A magyar miniszterelnök ma aljas módon a neonácik oldalára állt, belehazudott az egész ország arcába és uszított a meleg polgártársaim ellen.
Ezért én most a lehető legegyszerűbb és leggyermetegebb módon, matematikus olvasóink valószínűleg nem fognak megdícsérni érte, el fogom magyarázni az Entscheidungsproblem-et, ami az emberiség egyik legérdekesebb matematikai (filozófiai?) problémája, mely problémát egy bizonyos Alan Turing nevű brit, meleg, csodálatos matematikus oldott meg 1937-ben.
Szinte mese lesz, mert meseország mindenkié. Mindenkinek joga van arra, hogy megértse ezt, mert nincs meleg vagy heteroszexuális matematika, nincs meleg vagy heteroszexuális tehetség, nincs meleg vagy heteroszexuális bölcsesség, csak matematika van, tehetség és bölcsesség, ahogy nincs meleg vagy heteroszexuális Magyarország sem, csak Magyarország... nincs. Ma nincs, egyszer talán majd lesz.
******************************************************
Az Entscheidungsproblem valójában egy filozófiai probléma és az emberi elme határairól szól. Talán többről. Talán az isteni elme határairól is. Megválaszolhatunk-e minden kérdést? Mindenható-e a logika? Mindenható-e az elme?
Persze nem várhatjuk el, hogy logikai eszközökkel válaszoljunk olyan kérdésekre, minthogy mi az Élet értelme vagy létezik-e Isten. Az Entscheidungsproblem arról szól, hogy létezik-e egy olyan titokzatos algoritmus, amely logikai állításokról dönti el, hogy igazak vagy hamisak.
Turing (és tőle függetlenül Alonzo Church filozófus-matematikus) bizonyította be, hogy az elménknek is vannak határai, a mindent megoldó algoritmus nem létezik. És most a kedves Olvasó ezt meg fogja érteni. Igen, az egyik legérdekesebb matematikai/filozófiai problémát pont a mai napon fogja megérteni a kedves Olvasó.
*******************************************************
Tegyük fel egy pillanatra, hogy létezik egy ilyen csodálatos algoritmus. Ez nyilván azt jelentené, hogy egy nagyon egyszerű feladatot is meg tudna oldani. El tudná dönteni egy számítógépprogramról (mondjuk BASIC nyelvű), hogy a következő két állítás közül melyik igaz rá:
X. A program egy NULLÁK-ból és EGYES-ekből álló végtelen sorozatot ír ki.
Y. A program nem ezt teszi. Bármi mást, csak nem ezt. Lehet, hogy hibaüzenettel leáll, lehet, hogy egyszer leír egy A betűt, vagy csak véges sok NULLÁT és EGYEST. Jegyezzük meg, hogy minden, a billentyűzeten leírható, jelsorozatot potenciális programnak észlel az algoritmus, József Attila Mama című versét is. Hát azt pont egy Y típusú jelsorozatnak.
Az algoritmusunk tehát megérti a programokat anélkül, hogy lefuttatná őket, hiszen a döntését véges idő alatt kell meghoznia. Nem olyan egyszerű ez. Képzeljük el, hogy a program, amiről az algoritmusnak el kell döntenie, hogy az X vagy az Y típusba tartozik, a következő. Elkezdi sorban nézegetni a számokat és amikor talál egy ikerprímet, mint például a 3,5 vagy a 11,13 , akkor leír egy EGYEST. Ilyen programot kilencéves gyerekek is tudnak írni. De most gondoljon bele az Olvasó. Ha az algoritmusunk el tudná dönteni, hogy ez a program X vagy Y típusú, akkor ezzel meg tudná oldani az ikerprímszámsejtést (mármint, hogy van-e végtelen sok ikerprímpár), ami a matematika egyik leghíresebb megoldatlan problámája.
Valaki azt állítja, hogy a birtokában van a fenti SZUPER algoritmus. Mi most kimutatjuk, hogy téved. Nem hazudik, mint Magyarország miniszterelnöke, csak téved.
A fent már említett kilencéves gyereket megkérjük arra, hogy írjon egy SZIMPLA nevű programot/algoritmust, ami felsorolja az összes olyan véges jelsorozatot, amit a billentyűzeten egyáltalán le lehet írni. Ezek között a jelsorozatok között lesz a XH3%777 , a FUCKYOU (igen, külön neki), és egy olyan jelsorozat is, ami egy valóságos számítógépprogram és outputként kiír végtelen sok egyest.
A SZIMPLA algoritmus outputja tehát a J(1), J(2), J(3),... végtelen sorozat, amelynek minden eleme egy véges jelsorozat, és minden jelsorozat pontosan egyszer szerepel az outputban.
Ezek után megépítjük a HIPER nevű algoritmust. Ami a következő módon működik. A SZUPER algoritmusnak odaadjuk J(1)-et. Ha SZUPER azt mondja, hogy J(1) egy Y típusú jelsorozat, akkor HIPER kiír egy 0-t. Ha SZUPER azt mondja, hogy J(1) egy X típusú jelsorozat, akkor addig futtatjuk J(1)-et, amíg le nem írja az ELSŐ számot (mert tudjuk, hogy végtelen sok NULLÁT vagy EGYES-t írna le, ha hagynánk bomolni). Ha ez a szám 0, akkor a HIPER kiír egy 1-t. Ha 1, akkor a HIPER kiír egy 0-t.
Ezek után a SZUPER algoritmusnak odaadjuk J(2)-t. Ha SZUPER azt mondja, hogy J(2) egy Y típusú jelsorozat, akkor HIPER kiír egy 0-t. Ha SZUPER azt mondja, hogy J(2) egy X típusú jelsorozat, akkor addig futtatjuk J(2)-et, amíg le nem írja a MÁSODIK számot. Ha az 0, akkor a HIPER kiír egy 1-t. Ha az 1, akkor a HIPER kiír egy 0-t.
Ezek után a SZUPER algoritmusnak odaadjuk J(3)-t. Ha SZUPER azt mondja, hogy J(3) egy Y típusú jelsorozat, akkor HIPER kiír egy 0-t. Ha SZUPER azt mondja, hogy J(3) egy X típusú jelsorozat, akkor addig futtatjuk J(3)-at, amíg le nem írja a HARMADIK számot. Ha az 0, akkor a HIPER kiír egy 1-t. Ha az 1, akkor a HIPER kiír egy 0-t.
És így tovább.......
A HIPER algoritmus tehát egy X típusú jelsorozat, hiszen az outputja egy NULLÁK-ból és EGYESEK-ből álló végtelen sorozat.
És akkor mi van, kérdezi most az Olvasó?
HIPER egy jelsorozat, tehát a kilencéves gyerek SZIMPLA nevű programja felsorolta. Ő volt J(n), ahol n esetleg egy nagyon nagy szám, százbillió számjegyből áll, talán annál is több számjegyből. HIPER X típusú jelsorozat, tehát az outputjának n-edik karaktere vagy egy NULLA vagy egy EGY.
Tegyük fel, hogy ez a T nevű érték NULLA.
Emlékezzünk most vissza arra, hogy a HIPER outputjának mi is az n-edik jegye. Ha a J(n) nevű program X típusú, akkor a HIPER outputjának n-edik jegye pontosan akkor NULLA, ha a J(n) program outputjának az n-edik jegye EGYES. Dehát előbb beszéltük meg, hogy ez a bizonyos jegy, amit T-nek neveztünk, NULLA volt, akkor pedig mégse lehet NULLA.
Hoppácska.
Ha kétségbeesésünkben feltesszük, hogy a T nevű érték EGYES, akkor pont ugyanakkora bajba kerülünk. Más lehetőség pedig nincs. Ellentmondásba ütköztünk.
Tehát SZUPER nem létezik.
************************************************************
