 | Tämän artikkelin tai sen osankieliasua on pyydetty parannettavaksi. Voit auttaa Wikipediaaparantamalla artikkelin kieliasua. |
Busy beaver (suom. ”touhuaja”, kirjaimellisesti ”kiireinen majava”) on lukujono, jonka jäseninä on tietynTuringin koneen syöttämät maksimiarvot. Busy beaver -ongelman esitteli ensimmäisen kerran unkarilainen matemaatikkoTibor Rado vuonna1962. Busy beaver -lukujonoa pidetään nopeimmin kasvavana funktiona, joka voidaan ohjelmoida ja suorittaa koneellisesti.[1]
Turingin kone on yksinkertainentietokone, joka tulostaa nauhalle sarjan ykkösiä tai nollia riippuen koneelle syötetystä ohjeistuksesta. Koneeseen voidaan syöttää seuraavanlaiset ohjeet:
| 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 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ä ohjekorttejaja 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,....).[2]
Busy beaverin (lyhennetäänBB(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ä.[1]
| 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 | - |