A hódcsapda problémája
Lényeges szempont, hogy a szorgos hód-probléma szorosan kapcsolódik az úgynevezett leállási problémához, amelyet Alan Turing vetett fel 1936-ban. Ez arra vonatkozik, hogy lehetséges-e általános módon eldönteni, hogy egy adott számítógépes program valaha megáll-e, vagy örökké futni fog. Turing bebizonyította, hogy nincs ilyen univerzális módszer – vannak olyan programok, amelyeknél egyszerűen képtelenség ezt eldönteni.
A szorgos hód-játékot Rád Tibor magyar matematikus találta ki 1962-ben. A szabály egyszerű: adjunk meg egy Turing-gépet – ez egy nagyon egyszerű, formális program –, amelynek n darab szabálya lehet. Az a gép, amelyik a legtovább fut, mielőtt megáll, lesz a szorgos hód, az erre jellemző érték pedig BB(n). A keresés során minden lehetséges n-szabályos Turing-gépet ki kell próbálni, szimulálni kell, majd ki kell zárni azokat, amelyek végtelen ciklusba kerülnek vagy túl hamar leállnak.
Mindazonáltal a szabályok számának növelésével a lehetséges gépek száma és bonyolultsága elképzelhetetlenné válik. A haladáshoz trükkös algoritmusokra, egyedi szoftverre és elképesztő számítási teljesítményre van szükség. De még ez sem mindig elég: néhány gép futása annyira hosszú, hogy lehetetlen minden lépését szimulálni, ezért okos matematikai módszerekre van szükség.
Fordulópont a kutatásban
Az utóbbi évtizedekben rengeteg matematikus és hobbi kutató próbálta „meghódítani” a BB(6)-ot. Már 2007-ben is született új rekord: egy hat szabályos Turing-gép 3000 jegyű (!) számú lépést tett meg a leállásig – viszonyításképpen, hektáros papírlapra lenne szükség ennyi számjegyet leírni. Ám hamar kifulladt a verseny, míg 2010-ben egy fiatal szlovák informatikus, Pavel Kropitz saját szoftverével tízszer hosszabb futású gépre bukkant: az új rekorder 30 000 jegyű volt.
Innen már nem volt visszaút – az egész közösség vad rekordhajszába kezdett, ahol a gépek futási ideje gyorsan túlszárnyalta a megszámlálható világot. Olyan új műveletek (tetráció, pentáció) jelentek meg, amelyek a matematika megszokott eszköztárán is messze túlmutatnak: például a 10↑↑15 azt jelenti, hogy tizenötször egymásra halmozzuk az exponenciálást, így nem egyszerűen hatalmas, hanem leírhatatlanul nagy szám lesz az eredmény.
Új korszak, új módszerek
2022-ben egyetemisták és amatőrök megalapították a Szorgos Hód Kihívás (Busy Beaver Challenge) nevű közösséget, amely célul tűzte ki BB(5) pontos bizonyítását. Ennek révén született meg a jelenleg ismert legnagyobb rekord is BB(6)-ban, ahol már annyi nulla szerepel, hogy ha a tízeseket sorba írnánk, a szám hosszúsága 40 km lenne – ha egytucat betűméretű szedéssel dolgoznánk.
A mesterséges intelligenciával támogatott keresés során új típusú gépektől is vártak meglepetéseket: például a shift overflow counter nevű elvet követő gépek más logika szerint halogatják a leállást, mint az eddig ismertek. Ezek közül több is közel került az addigi csúcshoz, majd egy mxdys nevű, titokzatos dizájnertárs bejelentette: egy gép már annyit lépett, hogy a szükséges leíró számot még a legrövidebb matematikai formában sem lehet értelmesen kifejezni.
Ennek fényében a BB(6)-ra vonatkozó jelenlegi alsó becslést is csak pentációval, három felnyilazással (↑↑↑) lehet matematikailag leírni; ez elképzelhetetlenül hatalmas – nemcsak papíron, de az univerzumban sem fér el.
Örök rejtélyek és új problémák
Persze távolról sincs vége a történetnek. Egy „antihidra” néven futó, hat szabályos program például olyan komplex viselkedést mutatott, hogy nagy valószínűséggel soha nem áll le – de ezt még senkinek sem sikerült bizonyítani. Ráadásul a kérdés összefügg a híres Collatz-sejtéssel (Collatz conjecture), amely a matematikai világ egyik legnagyobb rejtélye.
A kutatók szerint több ezer hat szabályos Turing-gép vár még felfedezésre, s mindegyik újabb lehetőséget rejt a világegyetem leghosszabb, mégis legegyszerűbb programjainak felkutatására.
A valóságon túl is akad tehát még feladat: hiszen, ahogy az egyik lelkes kutató megjegyezte – a matematika legfőbb mozgatórugója a szépség és a játékosság. Ebben a játszmában mindig akad még egy ismeretlen szint.
