Busy beaver

Wikipediasta
Siirry navigaatioon Siirry hakuun

Busy beaver (suom. ”touhuaja”, kirjaimellisesti ”kiireinen majava”) on lukujono, minkä 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 nopeiten 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:

  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) [1]
Esimerkki koneelle syötetystä ohjeistuksesta:[muokkaa | muokkaa wikitekstiä]
'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[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, koska osa mahdollisista ≥5 kortin koneista on edelleen käynnissä. Näistä koneista ne versiot jotka muodostavat komentosarjan, mitkä kiertävät kehää voidaan postaa, koska tiedetään, etteivät ne koskaan pysähdy. Kuitenkin on olemassa ≥5 ohjekortin koneita, jotka ovat sekä 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 -

[1][3]

Lähteet[muokkaa | muokkaa wikitekstiä]

  1. a b c d Busy Beaver Turing Machines - Computerphile Computerphile. 02.09.2014. Youtube. Viitattu 06.09.2020. (englanniksi)
  2. ["https://catonmat.net/busy-beaver" The Busy Beaver Problem] "Catonmat.net". (englanniksi)
  3. ["https://oeis.org/A028444" "Lukujono A028444"] "30.08.11". "Online Encyclopedia of Integer Sequences".