ビジービーバー
busy beaver
計算不可能な関数の一つ
いかなる計算可能関数よりも急速に増大する
ビジービーバーが計算不可能であることの証明
例
BB3 ref
状態数が3つのBusy Beaverのチューリングマシン
https://gyazo.com/e570a9e1a5a35350fef9f27c34506d5f https://en.wikipedia.org/wiki/Turing_machine_examples#3-state_Busy_Beaver
Pはprintで、セルを1に書き換える
L, Rはヘッドの左右の移動
初期状態ではセルは全部0で、行ったり来たりしながら1に書き換える
最終的に6つの1ができた状態で停止する
https://gyazo.com/6acf6807ef2f47da6d75f7d8d019b030
矢印はヘッドの動きを表す
ヘッドをビーバーに、セル上の文字を木の枝に見立てると、ビーバーが上流と下流を行ったり来たりしながら木の枝を運んでダムを作るように見える
参考
https://ja.wikipedia.org/wiki/ビジービーバー
詳しいなーmrsekut.icon
https://googology.wikia.org/ja/wiki/ビジービーバー関数
https://nickdrozd.github.io/2021/01/26/spaghetti-code-conjecture.html