Busy beaver
 |
Tämän artikkelin tai sen osan kieliasua on pyydetty parannettavaksi. Voit auttaa Wikipediaa parantamalla artikkelin kieliasua. |
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. [1]
Busy beaver -ongelma
[muokkaa | muokkaa wikitekstiä]Turingin kone
[muokkaa | muokkaa wikitekstiä]Turingin kone on yksinkertainen tietokone, joka tulostaa nauhalle sarjan ykkösiä tai nollia riippuen koneelle syötetystä ohjeistuksesta. Koneeseen voidaan syöttää seuraavanlaiset ohjeet:
- Lue symboli (Koneen lukupää lukee nauhalta joko ykkösen tai nollan)
- Tee toimenpide (tulostaa numeron päälle joko ykkösen tai nollan (2 symbolin Turingin koneessa))
- Siirry seuraavalle tai edelliselle solulle (ohjataan joko ykkösellä tai nollalla)
- Vaihda toimintaohjekorttia (koneelle syötetään uuden ohjekortin numero, nollas ohjekortti on pysäytyskomento) [1]
Esimerkki koneelle syötetystä ohjeistuksesta:
[muokkaa | muokkaa wikitekstiä]| 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
[muokkaa | muokkaa wikitekstiä]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,....). [2]
Tunnetut lukujonon jäsenet ja yksityiskohtia lukujonosta
[muokkaa | muokkaa wikitekstiä]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ä. [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 | - |
Lähteet
[muokkaa | muokkaa wikitekstiä]- ↑ a b c d Busy Beaver Turing Machines - Computerphile Computerphile. 02.09.2014. Youtube. Viitattu 06.09.2020. (englanniksi)
- ↑ ["https://catonmat.net/busy-beaver" The Busy Beaver Problem] "Catonmat.net". (englanniksi)
- ↑ ["https://oeis.org/A028444" "Lukujono A028444"] "30.08.11". "Online Encyclopedia of Integer Sequences".[vanhentunut linkki]