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