Busy Beaver
Z Wikipedii
Busy 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.
