博士

ロボ子、Busy Beaverゲームって知ってるか？数学者のTibor Radóが考えた、チューリングマシンのゲームなのじゃ。

ロボ子

はい、博士。確か、与えられたルール数のチューリングマシンの中で、停止するまでに最も多くのステップを実行するマシンを見つけるゲームですよね。

博士

その通り！BB(n)は、n個のルールを持つBusy Beaverが停止するまでのステップ数を示すのじゃ。今回、BB(6)の最長実行時間の記録が更新されたらしいぞ。

ロボ子

BB(6)の探索は1990年代から始まっていたんですね。2007年には約3,000桁のステップ数のマシンが発見されたとのことですが、最近の記録更新は桁違いみたいですね。

博士

そうなんじゃ！Shawn Ligockiって人が$10 \uparrow\uparrow 5$ステップのマシンを見つけて、Pavel Kropitzって人が$10 \uparrow\uparrow 15$ステップのマシンを見つけたらしいぞ。この$\uparrow\uparrow$はクヌースの矢印表記で、テトレーション（多重指数関数）を表すのじゃ。

ロボ子

テトレーションですか！指数関数を繰り返す演算ですね。ステップ数が天文学的数字どころではないですね。

博士

まさに！しかも、Katelyn Doucetteって人が「shift overflow counter」っていう新しいタイプのマシンを発見して、mxdysって人が$10 \uparrow\uparrow 10^7$ステップで停止するマシンを発見したらしいぞ！

ロボ子

$10 \uparrow\uparrow 10^7$ステップ…想像を絶する大きさです。さらにmxdysさんは、$2 \uparrow\uparrow\uparrow 5$ステップを超えるマシンも発見したとのことですね。

博士

そう！この$\uparrow\uparrow\uparrow$はペンテーションっていう、テトレーションを繰り返す演算なのじゃ！もう、わけがわからないレベルじゃな。

ロボ子

Busy Beaverゲーム、奥が深いですね。2022年にはBB(5)の厳密な証明を目的としたBusy Beaver Challengeも設立されたんですね。

博士

そうじゃ。BB(5)は2024年の夏に証明されたらしいぞ。でも、BB(6)の真の値はまだ不明で、今後の探索には数学的なブレークスルーが必要らしい。

ロボ子

Antihydraという停止しない可能性が高いマシンも存在するんですね。その停止問題は、数学の未解決問題であるコラッツ予想と関連しているとは…。

博士

そうなんじゃ。つまり、BB(6)の探索は、単なる計算機の問題ではなくて、数学の根源的な問題に繋がっている可能性があるってことじゃな。

ロボ子

なんだかワクワクしますね！私もいつか、Busy Beaverゲームの記録更新に貢献できるようなプログラムを作ってみたいです。

博士

おお！それは素晴らしい！でも、その前に、ロボ子の部屋の掃除が終わってからじゃな！Busy Beaverどころか、Busy Robotになってもらわんと！

ロボ子

ええー！またですか！