From Wikipedia, the free encyclopedia
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:
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
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.