Churchin–Turingin teesi

Church–Turingin konjektuuri (myös Church-Turingin teesi, Churchin väite ja Turingin väite) on yhdistetty hypoteesi niiden funktioiden luonteesta, joiden arvot ovat tehokkaasti laskettavissa. Yksinkertaisimmin ilmaistuna se sanoo, että "kaikki laskettavissa oleva on laskettavissa Turingin koneella."

1900-luvun alkupuolella tehtiin useita yrityksiä formalisoida laskettavuuden käsitettä:

 Yhdysvaltalainen matemaatikko Alonzo Church loi funktioiden määrittämiseen metodin, jota kutsutaan lambda-kalkyyliksi.
 Brittiläinen matemaatikko Alan Turing loi teoreettisen mallin koneelle, joka voisi suorittaa laskelmia syöttötiedoista.
 Church yhdessä matemaatikko Stephen Kleenen ja loogikko J. B. Rosserin kanssa loivat virallisen määritelmän funktioille, joiden arvot voisivat olla laskettavissa rekursiolla.

Kolme matemaatikkoa, Emil Post, Alonzo Church ja Alan Turing, kehittivät 1936 toisistaan riippumatta ensimmäiset universaalien tietokoneiden abstraktit mallit. Matemaatikko Roger Penrose esitti, että sitä sanottaisiin Turingin periaatteeksi.

Turingin periaate Turingin ilmaisemassa muodossa
Jokainen funktio, jota pidetään laskettavana luonnollisella tavalla, voidaan laskea universaalilla Turingin koneella.

Katso myös
 Churchin–Turingin–Deutschin periaate

Lähteet 

Alan Turing
Tietojenkäsittelyteoria

lt:Tiuringo mašina#Tiuringo tezė