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[szerkesztés]
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[szerkesztés]
- (2004. június 25.) „The Origins of the Turing Thesis Myth” (PDF). Lecture Notes in Computer Science (3526), 152–168. o. (Hozzáférés ideje: 2009. március 22.)
