Tegnapi hir, hogy Gordon Brown posztumusz bocsánatot kért Alan Turingtól és családjától. Alan Turingot homoszexualitása miatt kergették a halálba. Oscar Wilde túlélte a megaláztatásokat, ő nem.
Ezt a rövid posztot Alan Turing emlékének ajánlom.
Mi is az a Turing-gép? Nem más, mint egy primitív de primitívségében mégis univerzális számítógép. Pontosan ugyanazokat a számításokat tudja elvégezni, mint bármelyik mai kompjúter.
Van egy végtelen memóriaszalag (legyen esetleg rögtön kettő), amire felírunk egy programot. A gép elkezdi olvasni a memóriaszalagokat, azokon lépegetni tud, azt át tudja írni, és minden lépése csak a memóriaszalagon éppen elolvasott bittől, illetve a gép aktuális állapotától függ. Bármilyen különös, nagyjából tényleg így működik egy számítógép.
Képzeljük el, hogy megnézhetünk egy ilyen programot, és meg akarjuk tudni, hogy mi fog történni. Néha egyszerübb dolog végiggondolni, mint lefuttatni. Például a program kiindul a 2-es számból, az aktuális számot megszorozza kettővel, és akkor áll le, ha 3-ra végződő számot kap.
A legegyszerübb matematikai állítások úgy néznek ki, hogy írunk egy programot és megkérdezzük, mi történne, ha lefuttatnánk. Leállna-e a gép egy idő után vagy sem? Az a kérdés, hogy az előző program leáll-e, pontosan azt jelenti, létezik-e 3-ra végződő hatványa a kettőnek. És nem.
Már Descartes-ot is érdekelte, hogy van-e egy olyan módszer amellyel automatikusan fel lehet ismerni az igazságot. Hilbert a huszadik század elején ezt úgy fogalmazta meg, létezik-e olyan algoritmus, amely minden értelmes matematikai állitásról eldönti, hogy igaz vagy hamis.
Mégis, milyen lenne egy ilyen algoritmus? Ez egy T program lehetne, amit ha ráírunk egy Turing-gép egyik szalagjára, majd egy Q programot (mint afféle adatfile-t) ráírunk a Turing gép másik szalagjára, a számítógép a T programmel kielemzi a Q programot, és IGEN-nel válaszol, ha az lefutna (például mert teljesen hibás), és NEM-mel, ha az örökké futna.
Vegyük észre, hogy egy ilyen T program elég okos lenne. Tegyük fel, hogy a Q program semmi mást nem csinálna, csak sorban megnézné az összes lehetséges k-adik hatvány összegét minden, kettőnél nagyobb k-ra, és akkor állna le, ha találna egy olyan összeget, amelyik maga is k-hatvány. Ha a T program el tudná dönteni, hogy a Q program leáll vagy sem, akkor bizony képes lenne a Wiles-tétel (leánykori nevén a Nagy Fermat sejtés) megoldására.
Tegyük fel, hogy létezik egy ilyen szuperokos T program. Akkor nem nehéz belátni, hogy kell lennie egy olyan programnak is, amelyik a következőt csinálja: megkapja adatfile-ként a Q programot, és eldönti, hogy lefutna-e a Q program, ha sajátmagát kapná meg adatfile-nak. Ha ez megtörténne, akkor végtelen sokszor kiírná, hogy Q jó, ha nem történne meg, akkor kiírná, hogy Q rossz, majd leállna.
Tegyük fel, hogy a Q program megkapja sajátmagát adatfile-ként. Mit is jelent, hogy lefut? Ebben az esetben a program definíciójából következően végtelen sokszor kiírná, hogy Q jó, tehát mégsem futna le. Ha a Q program végtelen sok ideig futna, akkor viszont ki kellene írnia, hogy Q rossz, és le kellene állnia. Ez egy ellentmondás. Tehát a Q program — és így a mindent bizonyitó, szuperokos T program — nem létezhet. Ez Turing tétele az emberiség korlátairól.
Egy kicsit többet is mondhatunk. Az az állitás, hogy egy Q program lefut, ha megkapja saját magát inputként, nem más, mint egy matematikai tétel. Minden Q-ra van egy tételünk: egyes tételek persze végtelenül egyszerűek, mások bonyolultabbak. Megkérdezhetjük, hogy igaz-e egy ilyen tétel (akkor igaz, ha valahogy be tudjuk bizonyítani). Vegyük észre, hogy az nem lenne jó bizonyitás, ha Q-t ráírnánk a programszalagra, majd az adatszalagra és elindítanánk a gépet. Ezzel a módszerrel ugyanis csak azt tudjuk bebizonyítani, hogy a Q-hoz tartozó tétel igaz; azt nem, hogy a Q-hoz tartozó tétel hamis, annak a bizonyitása ugyanis (sajnos) végtelen hosszú ideig tartana.
Tegyük fel, hogy valahogy mégis be tudnánk bizonyítani (vagy cáfolni) minden egyes Q programhoz rendelt tételt. Ez csak azt jelentené, hogy amikor felsoroljuk az összes lehetséges bizonyítást (amit megtehetünk, hiszen azokat rekurzív módon felépíthetjük), egyszer meg fogjuk találni azt G(Q) szöveget, ami pontosan a Q program véges lefutásának bizonyítása vagy cáfolata.
Azaz megint van egy furcsa P programunk. Ez akkor áll le, ha Q-ról bebizonyítható, hogy soha nem áll le, ha sajátmagát kapja meg inputként, és végtelen ciklusba keveredik, ha Q-ról bebizonyitható, hogy leáll. Mi történik, ha P megkapja sajátmagát inputként? Tegyük fel, be tudjuk bizonyítani, hogy leáll. Akkor viszont nem állhat le. Ha be tudjuk bizonyítani, hogy nem áll le, akkor viszont a fentiek szerint leáll. Ez ellentmondás. De minek is mond ellent? Annak a ténynek, hogy a P-hez tartozó állitásnak van bizonyítása (vagy cáfolata). A P-hez tartozó nem bizonyítható és nem cáfolható. Good morning, Mr. Gödel!
Ezt csinálta meg Turing, akit egykor a halálba kergettek, akit ma megdobálnának Budapest utcáin. Márcsak az a kérdés, hogy azok, akik szívesen megdobálnák, vajon mit bizonyítottak be az életükben?
