ハクソク

世界を動かす技術を、日本語で。

忙しいビーバーの狩人たちが普通の数学を圧倒する数に達する

2025年8月23日原文(quantamagazine.org)

概要

  • 世界で最も長く動作する「シンプルなコンピュータプログラム」の新記録発見
  • Busy Beaver数（BB(n)）は理論計算機科学で最も難解な問題の一つ
  • BB(6)の下限値は通常の数値表記では到底書き表せない規模
  • 新たなアルゴリズムやコミュニティの協力で記録が次々と更新
  • 記録更新のたびに、桁違いの巨大数が次々と登場

ビジービーバー数：理論計算機科学の究極の謎

  • Busy Beaver数（BB(n)） は、n個のルールを持つ チューリングマシン が停止するまでに実行する最大ステップ数
  • 最初のBB(1)〜BB(4)は1960年代〜70年代に決定、BB(5)は2023年にオンラインコミュニティ「 Busy Beaver Challenge」によって確定
  • BB(6) は未だに正確な値不明、下限値だけでも宇宙の原子数を遥かに超える規模
  • BB(6)の下限値 は2022年以降、さらに信じられないほど大きく更新
  • Scott Aaronson （University of Texas, Austin）曰く「人間が理解できる範囲をはるかに超えている」規模

ビーバートラップ：停止問題とチューリングマシン

  • 停止問題 ：「任意のプログラムが停止するかどうか判定できるか？」という理論計算機科学の根本問題
  • Alan Turing が1936年に「一般的な解法は存在しない」と証明
  • チューリングマシン ：最小限のルールで動作する理論上の機械
  • Tibor Radó が1962年に「ビジービーバーゲーム」を考案、nルールで最長動作するマシンを探す競技
  • ルール数nが増えるごとに可能なマシン数が爆発的に増加、全探索は現実的に不可能

BB(6)記録更新の歴史

  • 1990年代〜2000年代、 Shawn Ligocki & Terry Ligocki 親子がBB(6)探索を開始、2007年に約3,000桁の記録達成
  • 2010年、スロバキアの学生 Pavel Kropitz が独自プログラムで新記録、30,000桁超え
  • 2022年、Ligockiが新ハードウェアで再挑戦し記録更新、Kropitzがすぐに記録を抜き返す競争が激化
  • 記録が「桁違い」から「次元違い」へ移行、10↑↑5（テトレーション）や10↑↑15といった巨大数が登場
    • 例：10↑↑3＝10の100億乗、10↑↑4になると宇宙の原子数より多い桁数

新時代の幕開け：コミュニティと新アルゴリズム

  • 2022年、 Tristan Stérin がBusy Beaver Challengeを設立しBB(5)の厳密証明を達成
  • mxdys という謎の貢献者がBB(6)の下限値を大幅に更新
  • Katelyn Doucette （Virginia Tech）が新種「シフトオーバーフローカウンター」型マシンを発見
  • mxdysが10↑↑10^7ステップ（1000万層のテトレーション）を記録、その後すぐにさらに大きな記録を樹立
  • 新記録は「ペンテーション」（三重矢印）という新たな演算を必要とする規模

超巨大数の世界

  • 加算→乗算→累乗→テトレーション→ペンテーション と演算が進化
  • 10↑↑n（テトレーション）のnが大きくなると、もはや物理的に表記不能
  • ペンテーションは「テトレーションの繰り返し」、人類史上最大級の数値表現
  • 最新のBB(6)記録は、既存のどんな表記法でも「人間の直感を遥かに超える」規模

ビジービーバー問題の魅力と今後

  • BB(n)の値決定は「停止問題」の困難さを如実に示す
  • 新たな探索手法やコミュニティ協力で、今後も記録更新が続く可能性
  • 理論計算機科学・巨大数・アルゴリズムの最前線を象徴する問題
  • 参加者たちが「美しい問題」「やみつきになる魅力」と語る知的挑戦

Hackerたちの意見

バジービーバーの話、めっちゃ好きなんだよね。高校の時にもうちょっと触れてたらよかったなぁ。ホルヘ・ルイス・ボルヘスの「バベルの図書館」を思い出す。バジービーバーの世界で他に面白い問題知ってる人いる？

└

フィクション的には、アーサー・C・クラークの「3001」に出てくるマンデルブロート迷路かな。> 彼らのアプローチはもっと微妙で、ホストマシンに宇宙の終わりまで完了できないプログラムを始動させるように説得した。マンデルブロート迷路は、その最も致命的な例だった。

└

https://www.scottaaronson.com/papers/bb.pdf この論文には、BBに関する興味深い予想がたくさん載ってるよ。

└

コラッツ予想 - これを解決する前から、コラッツのような問題に還元されるまでずっとそう言ってたと思う。

ああ、そうだ、全く新しい指数法則の数学だね。

ペンテーション？なんか可愛いね。他の大きな数好きには、デイビッド・メッツラーの素晴らしいプレイリストがあって、急成長する階層の深いところまで行けるよ。https://www.youtube.com/playlist?list=PL3A50BB9C34AB36B3 おすすめ。これらの驚異的に大きな数のほとんどは、アッカーマン関数のように再帰を基にしてる。アッカーマン関数に使うクヌースの上矢印の数を引数として持つんだ。それをそのスロットに入れて、どれだけクレイジーになるか考えると、めっちゃワクワクする。大きな数を指定するための仕組みが、私たちが使う数学のシステムの中で定義可能な限界をどれだけ早く探るかが面白いと思う。

└

信じられないくらい大きな有限数には、何か素晴らしいものがあるよね。人々は無限について熱く語るけど、私はこの宇宙で書ききれないくらい大きな有限数と比べると、無限は結構退屈な概念だと思う。

└

Numberphileは、計り知れないほど大きな有限数についての素晴らしい動画コレクションを作ってるよ：https://youtube.com/playlist?list=PLt5AfwLFPxWJ_FwchNAjB3xa8... これらのモンスターを調べたり比較したりするためのツールがすごく面白いんだ。

└

数学が好きな子供がいるなら、リチャード・シュワルツの「本当に大きな数」を超おすすめするよ。どんどん「大きなステップを踏む」方法をイラストでたくさん紹介してるから。「無限は思ってたよりも遠いよ。」

└

特定の数学の分野では、研究者の人生が「どの数字が一番大きいかを議論する（幼稚園）」→「数学を学ぶ」→「どの数字が一番大きいかを議論する（学術）」に凝縮されるのが面白いよね。

└

もう知ってるかもしれないけど、ビジービーバー関数は計算可能な関数よりも早く成長するんだ。だから、BB(6)の最も知られている下限はペンテーションだけで表現できるけど、一般的に言ってBB関数は急成長に関しては標準的な操作を超えているよ。

「ああ、そうだ、全く新しい指数法則の数学だね」っていうダウンボートされたコメントがある。皮肉は必要ないけど、実際これがこの記事の本質なんだよね。繰り返しの指数法則を深い数学的発見のように語ってるけど、そうじゃない。この記事は、バジービーバー数がなぜ面白いのかを説明するのを怠ってると思う。これって、HNに週に何回も載るクアンタマガジンの記事の症状だと思う。響きの良いタイトルと心地よい文章だけど、それ以上の本質はあまりない。

Hacker Newsで議論の続きを見る