Church–Turing-tézis

A számításelméletben a Church–Turing-tézis az 1930-as években megfogalmazott sejtés, mely szerint minden formalizálható probléma, ami megoldható algoritmussal, az megoldható Turing-géppel is, illetve bármilyen, a Turing-gép fogalmával azonos számítási teljesítményű absztrakt modellel, pl. lambda-kalkulussal is; azaz a Turing-gép (vagy ekvivalensei) a feladatmegoldó eljárások legáltalánosabb és a fenti értelemben legerősebb példája. A sejtést azért nem tételnek, hanem csak (hipo)tézisnek nevezik, mert nem matematikai tétel, ugyanis a „feladatmegoldó eljárás” nem mint definiált matematikai fogalom szerepel. A tézis inkább a számítógép-tudomány paradigmaszerű programja, semmint matematikai tétel.

Ugyanakkor szintén a harmincas években a „feladatmegoldó eljárás” fogalmát számtalan alakban sikerült formálisan megfoghatóvá tenni, de kiderült, hogy ezek a megfogalmazások is ekvivalensek a Turing-gépre épülő eljárásfogalommal. Ez azt jelenti, hogy a Turing-gép egy univerzális algoritmikus modell. Maga a Turing-gép tekinthető az algoritmus egy definíciójának. A tézis összefügg az erős mesterséges intelligencia elvi létével illetve lehetetlenségével is.

Nem ismerünk olyan algoritmikus rendszert, amelyről tudnánk, hogy erősebb a Turing-gépnél, és a legtöbb algoritmikus rendszerre bizonyított, hogy gyengébb, vagy ekvivalens. A bizonyítottan Turing-ekvivalens algoritmikus rendszerek a következők:

• asszociatív kalkulusok
• rekurzív függvények osztálya
• a lambda-kalkulus függvény-osztálya
• formális nyelvek legáltalánosabb, kötetlen osztálya
• C, LISP, Java, Prolog, Pascal stb. nyelven írt nem interaktív programok

Formálisan

Egy f: I* → I* parciális függvény kiszámítható ↔ f parciálisan rekurzív
Egy f: I* → I* (teljes) függvény kiszámítható ↔ f rekurzív
Egy L részhalmaza I*-nak nyelvre a nyelvbe tartozás problémája algoritmussal eldönthető ↔ L rekurzív

További információk

• Alice és Bob - 6. rész: Alice és Bob a kiszámíthatóság határán
• Alice és Bob - 7. rész: Alice és Bob egymillió dolláros kérdése
• Alice és Bob - 8. rész: Alice és Bob biztonsága
• (2004. június 25.) „The Origins of the Turing Thesis Myth” (PDF). Lecture Notes in Computer Science (3526), 152–168. o. [2008. május 15-i dátummal az eredetiből archiválva]. (Hozzáférés: 2009. március 22.)