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.Todellisuuden rakenne, s. 126 Matemaatikko Roger Penrose esitti, että sitä sanottaisiin Turingin periaatteeksi.Todellisuuden rakenne, s. 127

Turingin periaate Turingin ilmaisemassa muodossa
Jokainen funktio, jota pidetään laskettavana luonnollisella tavalla, voidaan laskea universaalilla Turingin koneella.Kvanttitietokone (kirja), s. 116

Katso myös
 Churchin–Turingin–Deutschin periaate

 Lähteet 

Luokka:Alan Turing
Luokka:Tietojenkäsittelyteoria

lt:Tiuringo mašina#Tiuringo tezė