ビジー ビーバー ゲームは、1962 年に数学者の Tibor Radó によって提案された理論的なコンピューター サイエンスの問題です。このゲームには、無限に長い紙にできるだけ多くの「1」を書き込むようにプログラムされた、ビジー ビーバーと呼ばれる特別なチューリング マシンが含まれます。 Busy Beaver ゲームでは、正の整数が与えられた場合、状態 (入力アルファベット、状態遷移関数などを含む) を持つすべてのチューリング マシンを考慮します。ゲームの目標は、空白の入力が与えられた場合に、停止するまでの実行に最も長い時間がかかり (または最も多くのステップを実行し)、同時に最も多くの 1 を出力するチューリング マシンを見つけることです。この出力内の 1 の数は、BB(n) で表される正の整数に対応するビジー ビーバー関数の値です。ここで、n はチューリング マシンの状態番号です。
2024 年 9 月、20 人以上の寄稿者からなるチームが、値 47,176,870 の 5 番目の Busy Beaver 番号 BB(5) を発見したと発表しました。この結果は、BB(5) の価値を最終決定することを目的としたオンライン コラボレーションである、Tristan Sterin が立ち上げた Busy Beaver Challenge プロジェクトの一部です。研究チームは、数学的証明の正確性を保証するために使用される正式な検証ツールである Coq Proof Assistant と呼ばれるソフトウェアを使用して、結果を検証しました。