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 muun muassa abstraktit koneet, virtuaalikoneet ja ohjelmointikielet. Määritelmiä:

Turing-vahvuus (Turing-powerful)

Järjestelmä, joka voi "laskea" eli suorittaa minkä tahansa Turing-laskettavan funktion kutsutaan Turing-vahvaksi (engl. Turing-powerful).

Turing-täydellisyys (Turing-complete)

Järjestelmä on Turing-täydellinen (engl. Turing-complete), 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. Churchin–Turingin 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

• Chomskyn hierarkia

Kirjallisuutta

• Brainerd, W.S. & Landweber, L. H. (1974), Theory of Computation, Wiley.
• Herken, Rolf (toim.): The Universal Turing Machine: A Half-Century Survey (1995), Springer Verlag.

Aiheesta muualla

• Giles, Jim: Simplest 'universal computer' wins student $25,000, New Scientist, 24. lokakuuta 2007. (englanniksi)
• Turing-täydellisyys C2-wikissä (englanniksi)