Turing-vahva

Laskettavuuden teoriassa esitetään useita toisiaan lähellä olevia termejä, jotka kuvaavat minkä tahansa tietokonejärjestelmän eli laskennallisen järjestelmän suorittamisen rajoja ("computational power"). Erilaisia tarkasteltavia järjestelmiä ovat mm. abstraktit koneet, virtuaalikoneet ja ohjelmointikielet. Määritelmiä:

Turing-vahvuus (Turing-täydellisyys)

Järjestelmä, joka voi "laskea" eli suorittaa minkä tahansa Turing-laskettavan funktion kutsutaan Turing-vahvaksi (Turing-powerful). Vastaavasti, järjestelmä on Turing-vahva, jos järjestelmä voi simuloida universaalia Turingin konetta.

Turing-yhteensopivuus (Turing equivalence)

Turing-vahvaa järjestelmää kutsutaan Turing-yhteensopivaksi jos jokainen funktio, jonka se voi suorittaa, on myös Turing-vahva. Toisin sanoen, se laskee täsmälleen kaikki saman luokan funktiot, jotka Turing-konekin tekee. Vastaavasti Turing-yhteensopiva kone on sellainen, joka voi simuloida universaalia Turingin konetta tai jota universaali Turing-kone voi simuloida.

Laskennan perusväittämässä, ns. Church-Turing -teesissä, on esitetty, että kaikki tunnetut Turing-vahvat järjestelmät ovat myös Turing-yhteensopivia.

Laskennallinen universaalius

Järjestelmän sanotaan olevan universaali tiettyyn järjestelmien muodostamaan ryhmään nähden, jos se voi suorittaa jokaisen näiden järjestelmien funktion (tai voi simuloida näitä järjestelmiä).

Katso myös

• Algoritminen informaatioteoria
• Chomskyn hierarkia
• Church-Turing -teesi
• Laskettavuuden teoria
• Pysähtyvät ja ei-pysähtyvät koneet

Kirjallisuutta

• Brainerd, W.S. & Landweber, L. H. (1974), Theory of Computation, Wiley.
• Giles, Jim: Simplest 'universal computer' wins student $25,000, New Scientist, October 24, 2007.
• Herken, Rolf (toim.): The Universal Turing Machine: A Half-Century Survey (1995), Springer Verlag.
• http://xkcd.com/505/ 'A Bunch of Rocks' (2008) An XKCD comic

Aiheesta muualla

• Turing-täydellisyys C2-wikissä (englanniksi)