Darbštusis bebras
Taškai: 12
Bebras Lukas yra labai stropus. Todėl bebras Justas pasamdė jį pripildyti maisto sandėlį. Sandėlyje yra ilga duobių eilė. Kiekviena duobė gali būti tuščia arba užpildyta.
Pasitraukdamas nuo tuščios duobės Lukas ją užpildo. Justas davė Lukui labai keistus nurodymus, kaip jis turi apeiti sandėlio duobes. Lukas pasirenka nurodymą pagal tai, (1) ar duobė, į kurią jis žiūri, yra tuščia ar užpildyta ir (2) kokia yra jo nuotaika (ramus ar linksmas).
Pagal nurodymus Lukas turi (1) eiti į kairę arba į dešinę prie kitos duobės ir (2) nustatyti, kokia yra jo nuotaika – rami ar linksma – arba iš viso SUSTOTI. Pavyzdžiui, nurodymas gali būti (kairė, linksmas).
Justas nurodymus Lukui surašė į lentelę:
Pradžioje visos duobės tuščios ir Lukas yra ramus.
Kiek duobių Lukas užpildys, kol SUSTOS?
Galime įžiūrėti, kad Lukas ir jo duobės atvaizduoja savotišką Turingo mašiną. Tiuringo mašinos veikimo principas remiasi abstrakčiu modeliu, kuris gali nusakyti visas skaičiavimo operacijas, nors tai įgyvendinti ir labai sudėtinga. Tiuringo mašiną sukūrė Alanas Tiuringas 1936 metais.
Šiame uždavinyje Lukas gali užpildyti keturias duobes ir turi dvi galimas būsenas (ramus, linksmas) – daugiau galimų būsenų nėra. Informatikoje nagrinėjama specifinis Tiuringo mašinos modelis, vadinamasis „darbštus bebras“, kuris atlieka maksimalų žingsnių skaičių tarp visų kurios nors klasės Tiuringo mašinų.
Daugiau apie šitokią Tiuringo mašiną galima paskaityti:
https://en.wikipedia.org/wiki/Busy_beaver
Įsigilinę matome, kad nėra svarbu, ar pirmasis ėjimas daromas į kairę ar į dešinę Luko ar Justo atžvilgiu.
Surašykime Luko darbų žurnalą:
