Church–Turing-tézis

A Wikipédiából, a szabad enciklopédiából
Ugrás a navigációhoz Ugrás a kereséshez

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]