Potraga za pronalaženjem najdugovječnijeg jednostavnog računalnog programa

Ali koliko teže? 1962. matematičar Tibor Radó izmislio je novi način da istraži ovo pitanje kroz što je nazvao Igra užurbana dabra. Za igru, započnite odabirom određenog broja pravila – saznajte taj broj n. Vaš je cilj pronaći n-Rule turing stroj koji se najduže pokreće prije nego što se na kraju zaustavi. Ovaj se stroj naziva zauzeti dabra i odgovarajući zauzeti broj Beaver, BB (n), je broj koraka koji je poduzimao.

U principu, ako želite pronaći užurbani daver za bilo koji dan nsamo trebate napraviti nekoliko stvari. Prvo nabrojite sve moguće n-Rule turing strojevi. Zatim koristite računalni program za simulaciju pokretanja svakog stroja. Potražite natpise da strojevi nikada neće zaustaviti – na primjer, mnogi će strojevi pasti u beskonačne petlje koji se ponavljaju. Odbacite sve ove ne-lomljene strojeve. Na kraju, zabilježite koliko koraka je svaki drugi stroj poduzeo prije zaustavljanja. Ona s najdužim vrijeme izvođenja je vaš užurban dabar.

U praksi ovo postaje škakljivo. Za početak, broj mogućih strojeva brzo raste sa svakim novim pravilom. Analiza njih sve pojedinačno bilo bi beznadno, pa ćete morati napisati prilagođeni računalni program za klasificiranje i odbacivanje strojeva. Neke se strojeve lako klasificiraju: ili se brzo zaustavljaju ili upadaju u lako prepoznatljive beskonačne petlje. Ali drugi trče dugo vremena bez prikazivanja očitog uzorka. Za ove strojeve problem zaustavljanja zaslužuje svoju strašnu reputaciju.

Što više pravila dodate, to vam je više računalne snage. Ali gruba sila nije dovoljna. Neki strojevi trče toliko dugo prije nego što ih je simuliranje, korak po korak, nemoguće. Potrebni su vam pametni matematički trikovi za mjerenje njihovih vremena.

“Poboljšanja tehnologije definitivno pomažu”, rekao je Shawn Ligockisoftverski inženjer i dugogodišnji lovac na Beaver. “Ali oni samo do sada pomažu.”

Kraj ere

Zauzet lovci na Beaver počeli su ozbiljno činiti problem BB (6) u 1990 -ima i 2000 -ima, tijekom zastoja u BB (5) lovu. Među njima su bili Shawn Ligocki i njegov otac Terry, primijenjeni matematičar koji je vodio svoj program pretraživanja u satima na moćnim računalima u Nacionalnom laboratoriju Lawrence Berkeley. U 2007. godini pronašli su stroj za Turingu sa šest pravila koji je oborio rekord za najduže vrijeme izvođenja: broj koraka koji je trebao prije zaustavljanja imao je gotovo 3000 znamenki. To je kolosalni broj bilo koje uobičajene mjere. Ali nije prevelika za zapis. U fontu od 12 bodova tih 3000 znamenki će pokriti jedan list papira.

Tri godine kasnije, slovački student preddiplomskog računalnog znanosti po imenu Pavel Kropitz odlučio je riješiti BB (6) Hunt kao viši projekt teze. Napisao je vlastiti program pretraživanja i postavio ga da se pokrene u pozadini na mreži od 30 računala u sveučilišnom laboratoriju. Nakon mjesec dana pronašao je stroj koji je trajao daleko duže od onog koji je otkrio Ligockis – novog “prvaka”, u Lingou užurbanih lovaca.

“Imao sam sreće, jer su se ljudi u laboratoriju već žalili na moju upotrebu CPU -a i morao sam se malo smanjiti”, napisao je Kropitz u izravnoj razmjeni poruka o Zauzet beaver Challenge Discord Server. Nakon još jednog mjeseca pretraživanja, oborio je vlastiti rekord strojem čije je vrijeme trajanja imalo preko 30 000 znamenki – dovoljno je napunio oko 10 stranica.