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 (). 

Turing-täydellisyys (Turing-complete)
Järjestelmä on Turing-täydellinen (), 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. 
 Turing-täydellisyys C2-wikissä 

Tietojenkäsittelyteoria