Cím:	Algoritmikus vagy véletlen? I. rész
Szerző(k):	ifj. Benczúr András
Füzet:	1992/január, 1 - 6. oldal	PDF  |  MathML
Témakör(ök):	Szakmai cikkek
Hivatkozás(ok):	1992/március: Megjegyzés az Algoritmikus vagy véletlen című cikkhez

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre. Algoritmikus vagy véletlen? I. rész   Talán mindenki elgondolkodott már azon, mit is jelent a véletlen fogalma. Például dobjunk fel egy pénzérmét $16$-szor, és írjuk fel a kapott fejek és írások sorozatát. Tételezzük fel, hogy $4$ kísérletben a következőket kapjuk:   ${\displaystyle \begin{array}{ccccccccccccccccc}{\displaystyle \text{(1)}}\hfill & \hfill {\displaystyle \text{ F}}\hfill & \hfill {\displaystyle \text{F}}\hfill & \hfill {\displaystyle \text{F}}\hfill & \hfill {\displaystyle \text{F}}\hfill & \hfill {\displaystyle \text{F}}\hfill & \hfill {\displaystyle \text{F}}\hfill & \hfill {\displaystyle \text{F}}\hfill & \hfill {\displaystyle \text{F}}\hfill & \hfill {\displaystyle \text{F}}\hfill & \hfill {\displaystyle \text{F}}\hfill & \hfill {\displaystyle \text{F}}\hfill & \hfill {\displaystyle \text{F}}\hfill & \hfill {\displaystyle \text{F}}\hfill & \hfill {\displaystyle \text{F}}\hfill & \hfill {\displaystyle \text{F}}\hfill & \hfill {\displaystyle \text{F;}}\hfill \\ {\displaystyle \text{(2)}}\hfill & \hfill {\displaystyle \text{ F}}\hfill & \hfill {\displaystyle \text{F}}\hfill & \hfill {\displaystyle \text{F}}\hfill & \hfill {\displaystyle \text{I}}\hfill & \hfill {\displaystyle \text{F}}\hfill & \hfill {\displaystyle \text{F}}\hfill & \hfill {\displaystyle \text{I}}\hfill & \hfill {\displaystyle \text{F}}\hfill & \hfill {\displaystyle \text{F}}\hfill & \hfill {\displaystyle \text{F}}\hfill & \hfill {\displaystyle \text{F}}\hfill & \hfill {\displaystyle \text{I}}\hfill & \hfill {\displaystyle \text{F}}\hfill & \hfill {\displaystyle \text{F}}\hfill & \hfill {\displaystyle \text{F}}\hfill & \hfill {\displaystyle \text{F;}}\hfill \\ {\displaystyle \text{(3)}}\hfill & \hfill {\displaystyle \text{ F}}\hfill & \hfill {\displaystyle \text{I}}\hfill & \hfill {\displaystyle \text{F}}\hfill & \hfill {\displaystyle \text{I}}\hfill & \hfill {\displaystyle \text{F}}\hfill & \hfill {\displaystyle \text{I}}\hfill & \hfill {\displaystyle \text{F}}\hfill & \hfill {\displaystyle \text{I}}\hfill & \hfill {\displaystyle \text{F}}\hfill & \hfill {\displaystyle \text{I}}\hfill & \hfill {\displaystyle \text{F}}\hfill & \hfill {\displaystyle \text{I}}\hfill & \hfill {\displaystyle \text{F}}\hfill & \hfill {\displaystyle \text{I}}\hfill & \hfill {\displaystyle \text{F}}\hfill & \hfill {\displaystyle \text{I;}}\hfill \\ {\displaystyle \text{(4)}}\hfill & \hfill {\displaystyle \text{ F}}\hfill & \hfill {\displaystyle \text{I}}\hfill & \hfill {\displaystyle \text{F}}\hfill & \hfill {\displaystyle \text{F}}\hfill & \hfill {\displaystyle \text{F}}\hfill & \hfill {\displaystyle \text{I}}\hfill & \hfill {\displaystyle \text{F}}\hfill & \hfill {\displaystyle \text{F}}\hfill & \hfill {\displaystyle \text{I}}\hfill & \hfill {\displaystyle \text{I}}\hfill & \hfill {\displaystyle \text{F}}\hfill & \hfill {\displaystyle \text{I}}\hfill & \hfill {\displaystyle \text{F}}\hfill & \hfill {\displaystyle \text{F}}\hfill & \hfill {\displaystyle \text{I}}\hfill & \hfill {\displaystyle \text{I.}}\hfill \end{array}}$   Az (1) esetben biztosan arra gyanakszunk, hogy az érme cinkelt, még (2) esetén is túl kevés az írások száma. Nem hisszük el a (3) eredményt sem, annak ellenére, hogy a dobásoknak pontosan a fele fej. A (4) esettel szemben azonban valószínűleg semmiféle kételyt nem támasztanánk. Gondoljuk viszont meg, hogy mind a $4$ eset egy-egy a lehetséges $2^{16}$ féle kimenetelből, valószínűségük tehát azonos. Így a jelenség nem a valószínűségszámítás nyelvén tűnik magyarázhatónak, inkább az algoritmusokén. Arról van szó, hogy az (1)‐(3) eseményeket túl szabályosnak, egyszerű algoritmussal leírhatónak tartjuk, szemben a szabálytalan, ,,véletlenszerű'' (4) esettel. Például (1) az ,,írj le $1$6 fejet'', (3) az ,,írj le $8$ FI-t'' utasítással megadható, de még (2) is, a három írás helyének megadásával, míg (4)-nél ilyen utasítás nincs. A cikkben foglalkozni fogunk az algoritmikusság és a véletlenszerűség összehasonlításával, az utóbbit jellemezzük, mint az előbbi ellentétét, s eközben az algoritmusok világának néhány meglepő, paradoxonszerű tulajdonságát fogjuk megismerni, sőt Gödel híres tételét is be tudjuk majd bizonyítani. Kezdés előtt egy figyelmeztetés. Mivel az algoritmusok, a logika területe csak igen fáradságosan és terjedelmesen tehető precízzé, gyakran fogunk intuíciónkra hagyatkozni. Talán nem lesz ez nagyon zavaró annak ellenére, hogy ki fog derülni, hogy olyan intuitívan egyszerű dolgok, mint pl. egy program végtelen ciklusba esése, számítógéppel kezelhetetlen probléma.   A bolha   Lássunk bevezetőül egy elemi feladatot: egy bolhát kell a sötétben elkapnunk úgy, hogy minden másodpercben átugrik a bolha egy másik helyre (nem látjuk, hogy honnan hová), mi pedig megpróbáljuk eltalálni azt a helyet és rácsapni. A bolhát csak akkor láthatjuk meg, ha elkaptuk. Célunk olyan stratégia kidolgozása, hogy véges idő alatt (amely a bolha szerencséjétől függően tetszőlegesen hosszú lehet) biztosan elkapjuk a bolhát, ha: I. A bolha a természetes számokon $\left(\text{N}=\left\{\mathrm{0,1,2}\text{...}\right\}\right)$ ugrál, a $0$-ból indulva, ismeretlen $\text{<span style="font-style: italic;">v</span>}\in \text{N}$ ,,sebességgel'', azaz másodpercenként $\text{<span style="font-style: italic;">v</span>}$ (egész) mezővel jobbra ugorva. II. A bolha ismét $\text{N}$-en ugrál, ismeretlen $\text{<span style="font-style: italic;">v</span>}\in \text{N}$ sebességgel, az ismeretlen ${\text{<span style="font-style: italic;">x</span>}}_0\in \text{N}$ pontból indulva. III. A bolha a sík természetes számokból álló koordinátájú pontjain ugrál, $v=\left(v_x\mathrm{,}{v}_y\right)$ ismeretlen sebességgel, az ismeretlen $\left(x_0\mathrm{,}{y}_0\right)$ pontból indulva. IV. A bolha egy ,,végtelen dimenziós téren'' ugrál, azaz olyan téren, amelynek pontjait, vagyis a bolha pillanatnyi helyzetét egy természetes számokból álló végtelen sorozat adja meg. A bolha a $\left(\mathrm{0,0,0}\text{...}\right)$ pontból induljon, és $\left(v_1\mathrm{,}{v}_2\mathrm{,}{v}_3\mathrm{,}\text{...}\right)$ sebességvektorának véges sok $v_i$ kivételével minden komponense $0$ legyen. (Másképpen: a bolha sebességvektora egy véges sorozat ‐ ha a végéről a végtelen sok $0$-t elhagyjuk.) V. A bolha $\text{N}$-en menekül, és bármely $t$ időpontban helyét egy számítógép által végrehajtott algoritmus adja meg, a $t$ értékének függvényében. VI. A bolháról semmit nem tudunk, véletlenszerűen ugrál $\text{N}$-en. Feladat. Továbbolvasás előtt adjunk stratégiát az I‐IV esetekre.   $***$ Ellenőrzésképpen, és mivel később is szükségünk lesz rá, következzenek a megoldások. I. A $t$ időpontban a bolha a $v\cdot t$ mezőn tartózkodik, tehát ha az $1$. másodpercben a $v=0$, a másodikban a $v=\mathrm{1,}\text{...}\mathrm{,}$ esetet próbáljuk ki, azaz a $t$-edik másodpercben a $t\cdot \left(t-1\right)$-edik mezőre csapunk, biztosan elkapjuk a bolhát. II. Most a bolha $\left(x_0+vt\right)$-n tartózkodik, célunk az összes $\left(x_0\mathrm{,}v\right)$ pár kipróbálása legalább egy-egy időpontban. Például az ábrán látható bejárást választhatjuk, $t=1$ esetén a $v=0$, $x_0=0$, $t=2$ esetén $v=0$, $x_0=1$, $t=3$-ra $v=1$, $x_0=\mathrm{0,}\text{...}$ stb. eseteket kipróbálva.     Fontos kiemelni a lényegét annak, amit csináltunk: kölcsönösen-egyértelmű leképzést adtunk meg $\text{N}$ és $\text{N}\times \text{N}$ (azaz a számpárok) között, amelyet jelöljünk $\phi :\text{N}\times \text{N}\to \text{N}$-nel, inverzét $\Psi =\left({\Psi }_1\mathrm{,}{\Psi }_2\right):\text{N}\to \text{N}\times \text{N}$-nel. Így a $t$-edik másodpercben p1. az $\left(x_0\mathrm{,}v\right)=\Psi \left(t-1\right)$ kezdeti értékekhez tartozó pozíciót próbálhatjuk ki, azaz a ${\Psi }_1\left(t-1\right)+{\Psi }_2\left(t-1\right)\cdot t$ pozíciót. III. Ezek után egyszerű a megoldás: $4$ paraméterünket $\left(v_x\mathrm{,}{v}_y\mathrm{,}{x}_0\mathrm{,}{y}_0\right)$ kódolhatjuk a $\phi (\phi \left(x_0\mathrm{,}{y}_0\right)$,$\phi \left(v_x\mathrm{,}{v}_y\right))$ képlettel és a bolhát az összes lehetséges kezdeti feltétel esetén elkapjuk. A $t$ időponthoz az $x_0={\Psi }_1\left({\Psi }_1\left(t-1\right)\right)$, $v_x={\Psi }_1\left({\Psi }_2\left(t-1\right)\right)$, $y_0={\Psi }_2\left({\Psi }_1\left(t-1\right)\right)$, $v_y={\Psi }_2\left({\Psi }_2\left(t-1\right)\right)$ kezdeti értékek tartozzanak. IV. Ismét megfoghatjuk a bolhát, ha fel tudjuk sorolni lehetséges sebességvektorait, a véges számsorozatokat, azaz $\text{N}$-nel ,,kódolni'' tudjuk azokat. Tegyük ezt a következőképpen. Írjuk fel a számsorozatot vesszőkkel elválasztva, azaz $11$ jel: a $0-9$ számjegyek és a vessző ( , ) felhasználásával. Tekintsük az így felírt jelsorozatban a vesszőt is számjegynek, így egy $11$-es számrendszerbeli számot kapunk. Megvan tehát a felsorolás, ha $\text{N}$ számainak $11$-es számrendszerbeli felírásából vissza tudjuk állítani a számsorozatot. Problémánk egyedül azzal lehet, hogy két vessző következhet egymás után egy $11$-es számrendszerbeli számban. Ekkor tekintsük egyszerűen $0$-nak a hiányzó számértéket. Ez a leképzés már nem egy-egy értelmű (pl.: $\mathrm{0,0}$-t állítja elő ${}_{\text{'}}{0}_{}=110$ és ${}_{\text{'}}{}_{}=10$ is, azonban igaz az, hogy minden időpontban kipróbálunk egy sebességvektort, és előbb-utóbb ki is próbáljuk az összeset, így a bolhát elkapjuk.   Az algoritmusok felsorolhatósága   Most térjünk rá az V‐VI. esetekre. Van-e egyáltalán különbség a kettő között? Vajon nem adható-e meg minden ,,ugrálási sorozat'' egy programmal? Ehhez először is tisztáznunk kell, mi is lehet a számítógép, amelyet bolhánk használ, azaz egy számunkra kezelhető, egyszerű de elég általános modellt kell alkotnunk. A gép álljon egy memóriából, amely a bemeneti és számítás közbeni adatokat, illetve a végeredményt tárolja, és egy programtárból, amely a végrehajtandó utasításokat. Legyen a memória korlátlanul nagy, azaz minden program használhasson tetszőlegesen sok memóriarekeszt, és minden memóriarekesz tárolhasson egy tetszőlegesen nagy természetes számot. A rekeszek legyenek sorszámozva. A gép programja álljon véges sok, egyesével növekedve sorszámozott sorból, minden sor a következő $5$ utasítás egyikét tartalmazhatja:     ${\displaystyle \begin{array}{cc}{\displaystyle \text{(1) NÖVEL<math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow></mrow><mrow><mi>k</mi></mrow></msub></mrow></math> }}\hfill & {\displaystyle \text{ - a <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>k</mi></math>-adik memóriarekesz tartalmát eggyel növeli;}}\hfill \\ {\displaystyle \text{(2) CSÖKKENT<math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow></mrow><mrow><mi>k</mi></mrow></msub></mrow></math> }}\hfill & {\displaystyle \text{ - a <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>k</mi></math>-adik memóriarekesz tartalmát eggyel csökkenti;}}\hfill \\ {\displaystyle \text{(3) KONSTANS<math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow></mrow><mrow><mi>k</mi></mrow></msub></mrow><mrow><mo fence="true" stretchy="true">(</mo><mrow><mi>n</mi></mrow><mo fence="true" stretchy="true">)</mo></mrow></math> }}\hfill & {\displaystyle \text{ - az <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>n</mi></math> számot a <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>k</mi></math>-adik memóriarekeszbe helyezi;}}\hfill \\ {\displaystyle \text{(4)UGRIK<math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow></mrow><mrow><mi>k</mi></mrow></msub></mrow><mrow><mo fence="true" stretchy="true">(</mo><mrow><mrow><msub><mrow><mi>n</mi></mrow><mrow><mn>1</mn></mrow></msub></mrow><mn>,</mn><mrow><msub><mrow><mi>n</mi></mrow><mrow><mn>2</mn></mrow></msub></mrow></mrow><mo fence="true" stretchy="true">)</mo></mrow></math> }}\hfill & {\displaystyle \text{ - ha a <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>k</mi></math>-adik rekesz tartalma <math xmlns="http://www.w3.org/1998/Math/MathML"><mn>0</mn></math>, az <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mi>n</mi></mrow><mrow><mn>1</mn></mrow></msub></mrow></math>-edik, különben}}\hfill \\ {\displaystyle }\hfill & {\displaystyle \text{ az <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mi>n</mi></mrow><mrow><mn>2</mn></mrow></msub></mrow></math>-edik soron folytatja a végrehajtást;}}\hfill \\ {\displaystyle \text{(5) STOP }}\hfill & {\displaystyle \text{ - program vége}}\hfill \end{array}}$     Ellenőrizhető, hogy ez az egyszerű gép is képes mindarra, amire ,,valódi'' testvérei, amelyek persze ,,csak'' korlátos memóriával rendelkeznek. Feladat. (Csak programozásban járatosabbak részére!) Írjunk programrészt a $k$-adik és az $l$-edik rekeszek összeadására. Az így kapott ÖSSZEAD$\left(k\mathrm{,}l\right)$ programrész segítségével pedig szorozzuk össze a $k$-adik és az $l$-edik rekeszek tartalmát. (Elkészíthetők további, a személyi számítógépen ismert (pl. BASIC) utasítások is a bolha számítógépén.) Ahhoz, hogy a bolha valóban alkalmazni tudja a gépet, már csak arra van szüksége, hogy programja a következő lépést időegység alatt elkészítse. Egy idealizációt (a végtelen memória feltételezését) már tettünk abból a célból, hogy minden program, méretétől függetlenül végrehajtható legyen, kössük ki még azt is, hogy időegység alatt szolgáltasson is eredményt. Ez az idealizáció sem tűnik ,,lehetetlenebbnek'', mint a végtelen memória. Közeledjünk az V. esethez a szokásos módon: próbáljuk meg felsorolni a bolha lehetséges stratégiáit.   1. tétel. A programok beszámozhatóak, azaz létezik olyan leképezés, amely minden természetes számhoz egy programot rendel, és minden programot előállít. Bizonyítás. Láttuk, hogy van olyan leképezés, amely minden $\text{N}$-beli számhoz egy véges sorozatot rendel. Elegendő tehát a véges sorozatokat továbbképezni programokká úgy, hogy minden program előálljon valamely véges sorozatból. Ekkor a két leképezés egymásutánja sorszámozza be a programokat. Tekintsünk egy programot, és hagyjuk el a sorszámozást (nincs a sorszámra szükség, hiszen úgyis egyesével növekszik). Írjuk ezután az utasításait egy sorba, az utasításokat és paramétereket vesszővel elválasztva. Pl. a 0 NÖVEL${}_1$ 1 UGRIK${}_2\left(\mathrm{0,2}\right)$ 2 STOP programból a NÖVEL ,1,UGRIK,2,0,2,STOP sorozat keletkezik. Ez számsorozattá alakítható, ha az utasításokat kódoljuk, pl. 0 ‐ NÖVEL 1 ‐ CSÖKKENT 2 ‐ KONSTANS 3 ‐ UGRIK 4 ‐ STOP Így minden programnak megfelel egy számsorozat, a fentinek a $\mathrm{0,1,3,2,0,2,4}$. Nézzük meg, hogyan tudunk fordítva, minden sorozathoz egy programot rendelni. Mindjárt az első számmal baj van: ha $4$-nél nagyobb, nem felel meg neki utasítás. Ezen segíthetünk, ha minden $4$-nél nagyobb vagy vele egyenlő számhoz a STOP-ot rendeljük, ha utasítás helyén áll. Ezután már van egy utasításunk. Tudjuk, hogy hány paramétere van (STOP-nak $0$, NÖVEL , CSÖKKENT-nek $1$, KONSTANS-nak $2$, UGRIK-nak $3$), így a sorozat következő megfelelő elemei lesznek e paraméterek, a következő sorozatelem pedig az új utasítás. Baj csak a végén lehet, ha egy utasítás paraméterei hiányoznak, mert előbb ért véget a sorozat. Ekkor nullákkal pótoljuk a hiányzó értékeket. Így minden sorozathoz hozzárendeltünk egy programot, és minden programot elő is állítottunk.$\square$ Ez megadja a választ az V. esetre: a $t$-edik másodpercben a $t$-edik programot a $t$ bemenettel kell végrehajtani, így a bolhát előbb-utóbb elkaphatjuk. Ez a gondolatmenet még egyszerűen számítógépesíthetőnek is tűnik, hiszen a $k$ számból előállítható a $k$-adik program, és ennek utasításait tudjuk szimulálni egy másik gépen. Erre később visszatérünk.   Cantor átlós eljárása, a megállási függvény   Vizsgáljuk most a VI. esetet. Ha a bolha szerencsés, ill. kémei vannak, megteheti, hogy mindig amellé a mező mellé lép, amelyre csapnánk, ezzel magának örök életet biztosítva. Tehát nemleges lesz a válasz e kérdésre, ami azt is jelenti, hogy nem lehet minden számsorozatot számítógéppel előállítani. Ha csak a $0-9$ helyekre ugrál a bolha, akkor is annyiféle végtelen sorozatot tud előállítani, mint ahány valós szám van $\left[\mathrm{0,1}\right]$-ben: írjuk egyszerűen tizedespont mögé sorra számjegyekként a bolha által elfoglalt mezők számát. Biztosan sokak számára ismert, hogy $\left[\mathrm{0,1}\right]$ intervallum valós számainak számossága nagyobb, mint $\text{N}$-é, nincsen olyan $\text{N}\to \left[\mathrm{0,1}\right]$ függvény, amely az egész $\left[\mathrm{0,1}\right]$-et felveszi. Tulajdonképpen ezt láttuk be az előbb, ám a módszert, Cantor átlós eljárását, célszerű még egyszer meggondolni. Tételezzük fel, hogy $\left[\mathrm{0,1}\right]$ valós számai felsorolhatók, például: ${\displaystyle \begin{array}{cc}\hfill {\displaystyle }& {\displaystyle \mathrm{0,}{a}_{11}{a}_{12}{a}_{13}\text{...}}\hfill \\ \hfill {\displaystyle }& {\displaystyle \mathrm{0,}{a}_{21}{a}_{22}{a}_{23}\text{...}}\hfill \\ \hfill {\displaystyle }& {\displaystyle ⋮}\hfill \end{array}}$ A bolhaüldözéssel analóg módon az $a_{tt}$ átlót vizsgáljuk. A $0\mathrm{,}\left(a_{11}+1\right)\left(a_{22}+1\right)\text{...}$ szám (ahol most $9+1$ definíció szerint $0$) nem szerepelhet a felsorolásban, hiszen ha abban a $t$-edik lenne, $t$-edik jegyének $a_{tt}\ne a_{tt}+1$-nek kellene lennie. Térjünk most vissza az V. esetre. Mi van, ha a bolha ekkor is kémkedik? Ha esetleg mi is számítógépet veszünk igénybe, előre megtudhatja annak programját, és ezt csak egy utasítással kell kiegészítenie a meneküléséhez: eggyel növelnie kell a végeredményt, hasonlóan az előző átlós eljáráshoz. Az előbb viszont meg tudtuk adni a stratégiát a bolha elfogására. Hol lehet a hiba? A válasz csak az lehet, hogy üldöző módszerünk programmal nem kiszámítható (tudjuk már, hogy vannak ilyen sorozatok). A $k$-adik program azonban szimulálható a $k$ szám ismeretében (aki nem hiszi, járjon utána: készítsen valamely gépen programot e feladatra). A másik lehetőség, hogy esetleg nem tudunk időben elkészülni következő lépésünkkel. Mi van, ha pl. a 0 UGRIK${}_0\left(\mathrm{0,0}\right)$ programot tekintjük éppen? Ez soha nem szolgáltathat eredményt, hiszen végtelen ciklusba esik, elrontja tehát a mi algoritmusunkat is. Ez jó magyarázatnak tűnik, ám mi lenne, ha kicsit ügyeskednénk és csak azokat a programokat hajtanánk végre, amelyek nem esnek végtelen ciklusba. Legyen pl. $H\left(k\mathrm{,}n\right)=\{{\displaystyle \begin{array}{c}\hfill {\displaystyle \mathrm{0,}\text{<span style="font-weight: normal;font-style: normal;"> ha a </span>}k\text{<span style="font-weight: normal;font-style: normal;">-adik program az </span>}n\text{<span style="font-weight: normal;font-style: normal;"> bemenetre végeredménnyel megáll,</span>}}\\ \hfill {\displaystyle \mathrm{1,}\text{<span style="font-weight: normal;font-style: normal;"> ha végtelen ciklusba esik.</span>}}\end{array}}$   Először tehát $H\left(k\mathrm{,}n\right)$-t kell kiszámítanunk, pl. kiszűrni a fentihez hasonló sorokat - (aki nem hiszi írjon rá algoritmust). Ha ez $0$, végrehajtjuk a programot, ha nem, egy időegységnyit pihenhetünk (vagy pl. a $0$-ra csapunk). Mivel már tudjuk, hogy ez lehetetlen, a következő konklúzióra kell jutnunk:   2. Tétel. $H\left(k\mathrm{,}n\right)$ számítógéppel nem kiszámítható.   Bizonyítás. Tulajdonképpen már elhangzott, de emeljük ki még egyszer a lényeget. Legyen $f\left(k\mathrm{,}n\right)$ a $k$-adik program kimenete az $n$ bemenet esetén, ha létezik, különben legyen pl. $0$. (A bolhaüldözés során tehát $f\left(k\mathrm{,}k\right)$-t kell meghatároznunk.) Ha $H\left(k\mathrm{,}k\right)$ kiszámítható volna, akkor $f\left(k\mathrm{,}k\right)$ is, hiszen először $H\left(k\mathrm{,}k\right)$-t meghatározva a $k$-adik programot csak akkor kell végrehajtani, ha valóban eredményt is szolgáltat. Legyen $g\left(k\right)=f\left(k\mathrm{,}k\right)+1$. Indirekt feltevésünk szerint ez is egy program, pl. az $l$-edik. Így $f\left(l\mathrm{,}l\right)=g\left(l\right)=f\left(l\mathrm{,}l\right)+\mathrm{1,}$ ellentmondás. $\square$   A számítógépek védelmében   Mielőtt azt gondolnánk, a számítástechnikusoknak bealkonyult, sosem lesz mesterséges intelligencia, hiszen íme egy feladat: ,,könnyedén'' megtaláljuk egy programban a végtelen ciklusokat, ám a gép mégsem boldogul vele; mi lenne, ha a program a következő volna: soroljuk fel az összes számnégyest (pl. a $\phi \left(\phi \left(x\mathrm{,}y\right)\mathrm{,}\phi \left(z\mathrm{,}n\right)\right)$ segítségével), és addig maradjunk ciklusban, amíg az $x^n+y^n=z^n$ összefüggés fenn nem áll köztük. A híres Fermat sejtés tehát csak speciális  esete $H\left(k\mathrm{,}n\right)$ meghatározásának! Általában is érdekes vizsgálni azt az esetet, amikor a bolha menekülőprogramja diofantoszi egyenletek (egész együtthatós polinomok) egész gyökeit adja meg. Hilbert (1862-1943), korának nagy matematikusa, az 1900-as Nemzetközi Matematikus konferenciára általa fontosnak ítélt feladatok egy listáját készítette el. A 10. problémája éppen az volt, hogyan dönthető el egy diofantoszi egyenletről, hogy van-e gyöke. Sokak közreműködésével csak 1961-től kezdett el érni annak bizonyítása, hogy nincs általános módszer (azaz számítógépesíthető algoritmus) e feladatra. Még egy érv a most kissé ellentmondásosnak tűnő algoritmuselmélet védelmében. Tulajdonképpen ,,megbukott'' az az idealizáció, hogy minden program időegység alatt végrehajtható. A bolhának csak olyan programválasztása lehet, amely minden bemenetre 1 időegység alatt kimenetet szolgáltat. Ha nekünk egy kicsit jobb gépünk van, soronként szimulálhatjuk a lehetséges programokat, és ha annyi lépéssel, amennyinél többet a bolha nem tud időegység alatt végrehajtani, nem kapunk eredményt, kiszűrtük a programot a lehetséges menekülési stratégiák közül. A bolha viszont a mi programunkat nem hajthatja végre, hiszen az ő gépe lassabb a miénknél.