KÍSÉRLETEK A SMULLYAN-GÉP
PONTOS DEFINIÁLÁSÁRA

Legyen az 1. számú Gép olyan, hogy válogatás nélkül mindent kinyomtat, méghozzá lexikografikus sorrendben. Ez olyan sorrend, ahogyan a számokat írjuk le egytõl akármeddig. Tehát 1, 2, 3 ... 10, 11, 12 ... 20, 21, 22 ... 30, 31, 32 ... 100, 101, 102 ... 110, 111, 112 ... És így tovább. Nekünk csak 3 jelünk van, így a dolog egyszerûbb. Tehát a szavak:
N, P, D, NN, NP, ND, PN, PP, PD, DN, DP, DD, NNN, NNP, NND, NPN, NPP, NPD, NDN, NDP, NDD, NNNN, NNNP, NNND, NNPN, NNPP, NNPD, NNDN, NNDP, NNDD és így tovább. Látjuk, hogy 3 db. egybetûs, 9 db. kétbetûs, 27 db. 3 betûs, és általában 3n db. n-betûs szavunk van. Melyek ezek közül a mondatok? Pl. PD (Azt jelenti hogy D printelhetõ, és ez igaz is), NPN (azt jelenti hogy N nem printelhetõ, és ez hamis), PDND (azt jelenti hogy ND Duplája, azaz NDND printelhetõ, és ez igaz) stb. Az 1. számú Gép nem törõdik a mondatok igazságértékével, ez tehát nem jó Smullyan-gép. De, mint látjuk, része lehet egy jó Smullyan-gépnek!

Építsük meg most a 2. számú Gépet! Ennek a hasában egy 1. számú Gép mûködik, és elõállít minden szót. A 2. számú Gép ezután egy második ütemben megvizsgálja az épp soron levõ szót, hogy mondat-e. Ha a mondat PDX, NPDX, NNPDX... stb. típusú, akkor nem nyomtatja ki, akármit is mond a mondat. Ezzel kiszûri a problémás eseteket, de sajnos sok érdekes esetet is! Ha a mondat PX, NPX, NNPX... stb típusú, és X nem D-vel kezdõdik, akkor X-et megkeresi a korábban kinyomtatott szavak közt. Mivel az 1. számú Gép lexikografikusan sorolja fel a szavakat, az X szó biztosan rövidebb, mint a PX, NPX, NNPX... szó, tehát ha kiprintelhetõ, akkor okvetlen szerepelnie kell! Ezek után a Gépnek már egyszerû a dolga: ha megtalálta az X szót, akkor a PX, NNPX, NNNNPX... mondatok igazak, és ki is printeli õket, az NPX, NNNPX... mondatok pedig hamisak, és nem printeli ki õket. Fordítva jár el, ha az X szót nem találta meg: a PX, NNPX... stb. hamis, és nem printeli ki, az NPX, NNNPX... stb. pedig igaz, tehát kiprinteli.
A 2.számú Gép már ki fogja printelni a PD, PPNN, PPPND szavakat, mert ezek igaz mondatok, de nem printeli a PDNP szót, mert ez PDX típusú, tehát problémás. Az NPNP nem mondat, ezért a gép nyugodt szívvel kiprinteli, tehát végül is a PDNP mondat igaz! Mégse lesz a 2. számú Gép által kiprintelve. Pont olyan ez, mintha a Mandinak csak az auráját printelném ki, és a legérdekesebb részt, a belsejét egyöntetûen feketére színezném. Ha ennél érdekesebb viselkedést akarok, akkor terveznem kell egy 3. számú Gépet, amely mindazt tudja, amit a 2. számú, de ezen felül még a PDX és NPDX mondatok közül is kiprintel valamennyit. Például, ha az X nem mondat, akkor a PDX nyugodt szívvel kiprintelhetõ, ugyanígy az NNPDX, NNNNPDX... is. Az NPDX viszont hamis mondat, nem printeli ki. A PDPDN mondat továbbra is problémás. Tehát tervezzünk egy 4. számú Gépet, és így tovább. Kérdés az, hogy vajon a végtelenedik Gép mit tud, és egyáltalán, van-e olyan Gép, amely mindent tud, ami egyáltalán tudható?

Smullyan könyve lényegében errõl szól: egyre jobb gépeket tervez, amelyek egyre többet tudnak matematikailag, ám a nemteljesség kísértete mindegyikben ott bolyong!
Sõt, ha egy matek rendszer konzisztens, úgy ezt nem tudja magáról bebizonyítani! Smullyan szerint ebbõl nem szabad arra a következtetésre jutni, hogy akkor egy matek rendszer konzisztenciája nem is bizonyítható! De bizony bizonyítható, csak nem a rendszer keretein belül! Tehát megintcsak ott tartunk, hogy a transzcendenciára szükség van! Ahhoz, hogy a 4. Gépünket megtervezzük, próbáljuk meg jobban kiismerni a lelkivilágát! A PDX-eket elemezzük. PDX XX láncokat fogunk követni.
PDPDPDN PDPDNPDPDN PDNPDPDNPDNPDPDN NPDPDNPDNPDPDN PD... Az aláhúzással azt jelöltem, hogy mely kifejezés Duplája lesz a következõ kifejezés. Látjuk, hogy egyre hosszabb szavak születnek, és mind vagy PD, vagy NPD kezdetû.
PDPPPN PPPNPPPN NPPPN N Ez egy véges lánc. N printelhetõ, ezért NPN hamis, és ugyanígy hamis az NPPPN is, emiatt PPPNPPPN is hamis, végül PDPPPN is hamis. Látjuk, hogy ezt véges lépésben el lehetett dönteni. Ha tehát PDX olyan, hogy X-ben nincs PD betûpár, akkor véges lépésben el lehet dönteni.
PDNPD NPDNPD NPDNPD itt ugyanazt kapjuk mindig. Itt PDNPD hamis, NPDNPD igaz, és egyik se printelhetõ!
Tudjuk, hogy a DD és az ND nem mondat, ezért printelhetõ. Ha a szavunkban szerepel a DD betûpár, akkor véges lépésben olyan szó kerül elõ, amely D-vel kezdõdik, tehát nem mondat, tehát printelhetõ. Így az eredeti szavunk igazságértéke megintcsak véges lépésben eldönthetõ. Példa: PDPDD PDDPDD DPDDDPDD, és ez nem mondat! Tehát printelhetõ, tehát PDDPDD igaz, printelhetõ, tehát PDPDD is igaz, printelhetõ.
Ha a szóban elõfordul az ND betûpár, akkor ez elõbbutóbb a szó elejére kerül, azaz a szó ilyen lesz: NDX, NNDX, NNNDX... és bármi is X, ez nem mondat, tehát printelhetõ.
Példa: PDPDND PDNDPDND NDPDNDNDPDND , és ez nem mondat.

Véges ciklusok is létrejöhetnek! Ezek ilyenek: A, B, C, E, F, G... jelölje az állításokat!
A: B printelhetõ, B: C printelhetõ, C: E nem printelhetõ, E: A nem printelhetõ.
Nos, melyiknek mi az igazságértéke? Nem printelhetõ mondat lehet igaz is és hamis is, ellenben printelhetõ mondat csak igaz lehet. Legyen pl. mind a négy igaz! Ekkor B és C printelhetõ, A és E nem printelhetõ. Legyen mind a négy hamis! Ekkor B és C nem printelhetõ, A és E printelhetõ. Azelsõ verzió ellentmondás nélkül megvalósulhat, de a második már nem, mert a hamis A és E printelhetõ lenne, ami lehetetlen! Ha pedig
A igaz, és B,C,E hamis: A, B és E printelhetõ, C pedig nem printelhetõ. De hát ez lehetetlen! Ha B hamis, akkor nem lehet printelhetõ! Tehát az igaz, hamis, hamis, hamis kombináció sem valósulhat meg. 16 kombináció van, végig lehet nézni, melyik valósulhat meg, és melyik nem. Itt tehát a gépnek döntési szabadsága van, szabadon választhat.
Hogyan konstruáljuk meg az A, B, C, E mondatokat? Nos, így: A=PB, B=PC, C=NPE és E=NPA. Tehát A=PB=PPC=PPNPE=PPNPNPA. Na, és itt lükkentünk a circulus vitiozusba! Szerencsére ezen segít a D alkalmazása! Így végül A=PPNPNP... és most az A helyett egy D-t írunk, és megismételjük a szót! A=PPNPNPDPPNPNPD! Ebbõl könnyen megkapjuk B, C, E-t: B=PNPNPDPPNPNPD, levettünk A elejérõl egy P-t.
C=NPNPDPPNPNPD, levettünk B elejérõl egy P-t. E=NPDPPNPNPD, levettünk C elejérõl egy NP-t. Látjuk, hogy az aláhúzott rész Duplája tényleg az A!
Ezzel a módszerrel akármilyen hosszú ciklusokat is tudunk csinálni.
A végtelen ciklusra pedig a PDPDN mondat a példa.
Most már tudjuk definiálni a 4. Gépet: Ugyanazt tudja, mint a 3. Gép, de ezen felül még ki tudja elemezni a PDX mondatok közül azokat, amelyben ND vagy DD betûpár van, és az olyan mondatokat is, amelyben csak egy PD betûpár van. A többi esetet, mint amilyen a PDPD, vagy a fenti ciklusok egyike, továbbra is problémásnak tekinti és nem printeli ki.
Az 5. számú gépet megtaníthatjuk arra, hogy a véges ciklusokat egy egyszerû szabállyal önkényesen döntse el, a 6. számú gépet pedig arra, hogy a végtelen ciklusokat is önkényesen döntse el. Világos, hogy még ezek sem a végsõ megoldás!

Eddig a gépeink csak azt tudták, hogy bizonyos szavakat kiprinteltek, tehát egy listát készítettek. De miért ne csinálhatnának a gépek több listát? Jelölje B a Bizonyítható Mondatok Halmazát, C a Cáfolható Mondatok Halmazát, I az Igaz Mondatok Halmazát és H a Hamis Mondatok Halmazát! Ekkor nyilván B I és C H. Ezen felül I és H diszjunktak. Smullyan könyvében ezek a halmazok fõszerepet játszanak. Vannak ezen kívül a predikátumok, azaz állítások is, amelyek halmazokat neveznek meg, és vannak olyan állítások is, amely szerint egy kifejezés egy bizonyos halmaz eleme.Ebben a világban az "ez a kifejezés nem eleme B -nek" egy igaz, de nem bizonyítható mondat. Ha hamis lenne, akkor "ez a kifejezés nem eleme B-nek" eleme lenne B-nek, ami nem lehet, mert hamis mondat nem bizonyítható. Tehát a kifejezés csak igaz lehet, és ennél fogva tényleg nem bizonyítható. A halmazok megnevezéséhez kitalálták a Gödel-számozást, ami szerint minden kifejezésnek van egy Gödel-száma, és ezek után a kifejezésekre úgy lehet hivatkozni, mint számokra. Formulákkal és kifejezésekkel számhalmazokat lehet konstruálni, és olyan mondatokat, ami szerint egy szám egy halmaz eleme vagy sem.
Ezek után a könyv fõ célja az, hogy megmutassa: a bizonyítható mondatok halmaza formulákkal megnevezhetõ, és így megnevezhetõ a halmaz komplementere is. Ezek után a Gödel-számok raffinált alkalmazásával megkonstruálja a Gödeli mondatot, amely azt állítja hogy õ maga nem bizonyítható. Ha hamis lenne, akkor állításával ellentétben bizonyítható lenne, de egy hamis mondat nem bizonyítható. Így a mondat igaz kell legyen, tehát tényleg nem bizonyítható. Smullyan ezt a mondatot hozza fel az eldönthetetlenség példájára. Tudniillik sem a mondat, sem a tagadása nem bizonyítható, tehát a mondat a rendszeren belül eldönthetetlen. Az én célom viszont annak megmutatása volt, hogy ez a mondat nem jó példa az eldönthetetlenségre, mert ez a mondat el van döntve: igaz! Nincs szabad választásom vele kapcsolatban. Az a feltevés, hogy ez a mondat hamis, ellentmon-dásra vezet, tehát a mondat csakis igaz lehet. Tehát el van döntve. Az igazi eldönthetetlen mondat így hangzik: "ez a mondat bizonyítható" ! Ez a mondat lehet igaz is, mert igaz mondatot lehet bizonyítani, és lehet hamis is, mert hamis mondatot nem lehet bizonyítani! Itt aztán tényleg szabad választásunk van!
Nevezhetjük elsõrendben eldönthetõnek azt a mondatot, ami véges lépésben bizonyítható vagy cáfolható, pontosabban véges lépésen belül visszavezethetõ egy olyan kifejezésre, ami nem mondat, tehát nincs is igazságértéke, így bizonyítás nélkül igaznak fogadjuk el.
Másodrendben eldönthetõ az a mondat, ami elsõrendben nem eldönthetõ, de az egyik igazságérték tételezése ellentmondásra vezet, tehát csak a másik igazságérték lehet érvényes! Ezek a nem bizonyítható, de igaz, és a nem cáfolható, de hamis mondatok.

Mondandónk végül oda csúcsosodott ki, hogy szabatosan definiáljuk, végül is mi az hogy bizonyítás és mi az, hogy igazság? Hívjuk segítségül Alfred Tarskit!