Encyklopedia w MarkpolReklama: wystrój wnętrzaBusy Beaver to maszyna Turinga o z góry zadanej liczbie stanów N, która zaczynając od pustej taśmy (same zera) generuje jak najdłuższy ciąg jedynek (lub też w innym sformułowaniu: wykonuje jak najwięcej kroków) po czym zatrzymuje się (maszyna, która nie zatrzymuje się jest dyskwalifikowana). Okazuje się, że zdefiniowana w ten sposób funkcja S(N) nie jest obliczalna, co więcej rośnie ona szybciej niż każda inna znana funkcja obliczalna. Początkowe wartości są znane i łatwo je wyznaczyć (np. S(3)=6), ale już dla N>4 znane są tylko dolne oszacowania wartości funkcji. Busy Beaver jest powiązany z problemami tego typu co problem Collatza. Zobacz też: przegląd zagadnień z zakresu matematyki Chcesz wypromować swoją stronę w internecie?? - nie zwlekaj pozycjonowanie w Luman.biz to rozsądny wybór |
|