„Turing-gép” változatai közötti eltérés

A [[Church–Turing-tézis]] egy, a múlt század harmincas éveiben megfogalmazott sejtés, miszerint minden formalizálható probléma, ami megoldható [[algoritmus]]sal, az megoldható Turing-géppel is; azaz a Turing-gép 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). 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 ill. lehetetlenségével is (vagyis, hogy az olyan szellemi minőségek, mint pl. az értelem, érzelem, gondolkodás; vajon csupán az algoritmusok tulajdonságai és elválasztható a harvertőlhardvertől, vagy sem.)