Delovni bober

Iz MaFiRaWiki

V računalništvu izraz delovni bober (v angleščini "Busy Beaver" izhaja iz pogovornega jezika, kjer označuje "marljivo osebo") pomeni Turingov stroj, ki dobi na vhodu prazen trak, opravi "veliko dela" in se nato ustavi, ko porabi vsa sredstva, ki jih ima na voljo. Stroj je namreč prostorsko ali časovno omejen. Soroden je koncept funkcije delovnega bobra ("Busy Beaver function"), ki kvantificira omejitve sredstev, ki so na voljo. Prvi ga je vpeljal Tibor Radó kot igro delovnega bobra ("Busy Beaver Game") v članku iz leta 1962, "O neizračunljivih funkcijah".


Igra delovnega bobra

V članku "O neizračunljivih funkcijah" iz leta 1962 predstavi Tibor Radó igro delovnega bobra na sledeč način: Na voljo imamo Turingov stroj nad dvojiško abecedo {0, 1} in n operacijskih stanj (pogosto jih označimo z 1, 2, ... n ali A, B, C ...) ter dodatno ustavitveno stanje ("Halt state").

Njegova definicija Turingovega stroja je bila sledeča:

  • Teče po neomejenem traku
  • Na vsakem koraku dva pogoja --
  1. trenutno stanje stroja (navodilo); in
  2. simbol, ki ga prebere bralna glava
-- definirata vsako od sledečih:
  1. simbol, ki ga zapiše v celico, kjer je glava (stroj lahko prepiše 1 v 0, 0 v 1, 1 v 1 ali 0 v 0)
  2. smer premika (levo ali desno, v tem modelu ni mogoče ostati v istem stanju); in
  3. stanje, v katerega se premakne (lahko ostane v istem)
  • Stroj se ustavi če in ko doseže posebno ustavitveno stanje

Sedaj začnemo s praznim trakom (v vsaki celici je simbol 0) in tabelo n navodil. Poženemo stroj; ko se ustavi, pogledamo število enic, ki jih pusti na traku.

Igra delovnega bobra z n stanji je v bistvu tekmovanje v iskanju Turingovega stroja z n stanji, ki pusti na traku izpisanih največ enic, ko se ustavi.

Da se udeležiš tekmovanja moraš najprej podati opis Turingovega stanja z n stanji in število korakov, ki jih naredi preden se ustavi (pomembno - če se stroj ne ustavi, ni splošnega algoritma, ki bi dokazal, da se ne bo ustavil)

Glej tudi

Osebna orodja