4.4. Church-Turing tézis

Ahogy azt a fejezet elején levő bevezetőben leírtuk, egy algoritmusra úgy tekintünk, mint egy függvényre, ami egy bemenő szóhoz (feladat) kiszámít egy kimenő szót (megoldás).

Az előző szakasz definíciói alapján a Turing-gépek is hasonló feladatot oldanak meg.

Felvetődik a kérdés, hogy melyek azok a feladatok, amelyek Turing-géppel megoldhatóak. Erre próbál választ adni a következő állítás.

4.13. Church-Turing tézis

Legyen  egy algoritmus, ami szavakat szavakká alakít, azaz .
Ekkor létezik egy  Turing-gép, amelyikre  esetén.

4.14. Megjegyzés

1. Amennyiben egy adott  bemenet esetén  nem áll meg,  nem 
   definiált. Ekkor feltételezzük, hogy  sem áll meg az adott szón.
2. A Church-Turing tézis mind a transzformációs, mind a döntési 
   feladatra értelmezhető. Ez utóbbi esetben az algoritmus kimenete 
   értelemszerűen nem egy szó, hanem egy döntés. (pl. igen-nem )

A Church-Turing tézis érdekessége, hogy a benne szereplő egyik fogalomnak (algoritmus) nincs matematikai definíciója. Ennek következménye, hogy az állításnak nem létezhet matematikai bizonyítása. Igazságértéke viszont van. Mit kezdhetünk akkor vele? Szokatlan módon, igazolni ugyan elvileg is lehetetlen, amennyiben azonban hamis az állítás, azt lehet bizonyítani. Ehhez elegendő találni egy olyan feladatot, amit valamilyen algoritmusnak elfogadható módszerrel meg tudunk oldani, Turing-géppel viszont bizonyíthatóan nem.

A tézis első megfogalmazása az 1930-as évekre tehető. Azóta cáfolni nem sikerült, annak ellenére, hogy jó páran próbálkoztak vele. Tipikus módszer erre az, hogy kifejlesztenek egy újabb algoritmusmodellt, majd megpróbálják belátni, hogy van olyan feladat, amit ennek segítségével meg lehet oldani, Turing-géppel viszont nem. A mai napig azonban minden modellről kiderült, hogy nem erősebb a Turing-gép modellnél. Ha a megoldható feladatok osztálya az adott modell esetén ugyanaz, mint a Turing-gépekkel megoldható feladatok osztálya, a kérdéses algoritmusleírást Turing-ekvivalensnek nevezik. A későbbiek során mi is megismerünk néhány újabb modellt (alapvetően a Turing-gép általánosításairól lesz szó), és be is látjuk Turing-ekvivalenciájukat. Nem véletlen az sem, hogy számtalan Turing-gép definíció létezik. Ekvivalenciájuk miatt elhanyagolható a köztük levő különbség, ezért több-kevesebb szabadságot engedhetünk meg, megtartva az eredeti ötletet: mindkét (vagy csak egy) irányban végtelen (vagy végtelenül nyújtható) szalag, véges állapotú regiszter.

A legismertebb Turing-ekvivalens algoritmusmodellek: