Busy beaver

Busy beaver (suom. ”touhuaja”, kirjaimellisesti ”kiireinen majava”) on lukujono, jonka jäseninä on tietyn Turingin koneen syöttämät maksimiarvot. Busy beaver -ongelman esitteli ensimmäisen kerran unkarilainen matemaatikko Tibor Rado vuonna 1962. Busy beaver -lukujonoa pidetään nopeimmin kasvavana funktiona, joka voidaan ohjelmoida ja suorittaa koneellisesti.

Busy beaver -ongelma

Turingin kone

Turingin kone on yksinkertainen tietokone, joka tulostaa nauhalle sarjan ykkösiä tai nollia riippuen koneelle syötetystä ohjeistuksesta. Koneeseen voidaan syöttää seuraavanlaiset ohjeet:

1. Lue symboli (Koneen lukupää lukee nauhalta joko ykkösen tai nollan)
2. Tee toimenpide (tulostaa numeron päälle joko ykkösen tai nollan (2 symbolin Turingin koneessa))
3. Siirry seuraavalle tai edelliselle solulle (ohjataan joko ykkösellä tai nollalla)
4. Vaihda toimintaohjekorttia (koneelle syötetään uuden ohjekortin numero, nollas ohjekortti on pysäytyskomento)

Esimerkki koneelle syötetystä ohjeistuksesta:

'Ohjekortti 1'

Kone lukee "0"	Kone lukee "1"
1	1
1	0
0	2

Ylläoleva kone muuttaa numeron ykköseksi, siirtää lukupäätä askeleen oikealle ja pysähtyy lukiessaan nollan (komentosarja 0110). Lukiessaan ykkösen kone muuttaa numeron uudelleen ykköseksi, siirtyy vasemmalle ja siirtyy ohjekorttiin kaksi (komentosarja 1102).

Busy beaver -sarja

Busy beaver on Turingin koneen erityistapaus, joka pohjautuu seuraavaan kysymykseen: Mikä on suurin lukumäärä ykkösiä, mitä kahden symbolin {0,1} Turingin kone voi tulostaa, kun koneella on n-määrä ohjekortteja ja kone pysähtyy? Tällöin sellaisia Turingin koneita, jotka tulostavat äärettömän määrän ykkösiä ei lasketa, vaan johonkin koneeseen syötetyistä ohjekorteista on sisällytettävä pysäytyskomento. On huomioitava, että jokaisen Turingin koneen alkuasetelmassa kaikki nauhan solut ovat "0"-asennossa (eli ...,0,0,0,0,0,....).

Tunnetut lukujonon jäsenet ja yksityiskohtia lukujonosta

Busy beaverin (lyhennetään BB(n)) jäsenten seulominen ja ratkaiseminen on todettu äärimmäisen hankalaksi, sillä osa mahdollisista ≥5 kortin koneista on pysyy käynnissä. Näistä koneista ne versiot, jotka muodostavat komentosarjan joka kiertää kehää, voidaan eliminoida, koska tiedetään, etteivät ne koskaan pysähdy. Kuitenkin, on olemassa ≥5 ohjekortin koneita, jotka ovat edelleen käynnissä eikä niiden ole toistaiseksi huomattu kiertävän kehää. Tämän vuoksi ≥5 kortin koneista on tiedossa vain alarajat, mitkä ovat toistaiseksi suurimpia löydettyjä lukumääriä ykkösiä.

Ohjekorttien lukumäärä "BB(n)"	Turingin koneiden lukumäärä	Maksimi äärellinen määrä ykkösiä
0	0	0
1	64	1
2	20736	4
3	16777216	6
4	256×108	13
5	2410	≥4098
6	2812	≥1010500
n	(4(n+1))2xn	-