Zajęty bóbr (ang. busy beaver) – 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 funkcja obliczalna.
Początkowe wartości są znane i łatwo je wyznaczyć (np. S(3)=21), 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. W istocie maszyny, które podejrzewa się o bycie pracowitymi bobrami wykonują pewną funkcję mocno zbliżoną do funkcji Collatza.
Zabawa w pracowitego bobra W swej publikacji z roku 1962, Tibor Radó prezentuje zabawę w pracowitego bobra jak następuje:
Rozpatrujemy maszynę Turinga o dwójkowym alfabecie {0, 1} i n stanach pracy (często określanych jako 1, 2, ... n lub A, B, C, ...) oraz dodatkowym stanie Stop.