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

BusyBeaver(6)はかなり大きいです

概要

  • Busy Beaver問題 の最新進展に関する解説
  • BB(6) の下限値が劇的に引き上げられた経緯
  • 巨大数の直感的な説明と ZFC独立性 への考察
  • 著者の個人的な心情や STOC 2025 参加の話題
  • コメントポリシー変更とブログ運営方針の共有

Busy Beaver問題の驚異的進展

  • Busy Beaver(BB)問題 は、与えられた状態数の チューリングマシン が停止するまでに実行できる最大ステップ数を求める問題

  • BB(6) は6状態2記号のチューリングマシンについての最大ステップ数の下限値

  • 2022年時点では BB(6) > 10^{36,534} が知られていたが、 Pavel Kropitz により BB(6) > ^{15}10 (10を15回テトレーション)に更新

  • その後、 BBchallenge チームの mxdysBB(6) > 10,000,000^{10} (10を1,000万回テトレーション)に証明を更新し、 Coq による正当性証明も実施

  • さらに、 BB(6) > ^{^{^{9}2}2}2 (2を9回テトレーションしたものをさらに2でテトレーション)という驚異的な下限値へと到達

    • 具体的には、 BB(6) ≥ 2ペンテーション5 (ペンテーションはテトレーションの繰り返し演算)

巨大数の直感的イメージ

  • 10,000,000^{10} の大きさを説明するため、 10,000,000^{10}個の砂粒 があれば、 観測可能な宇宙10,000,000^{10}回 満たすことが可能
  • この規模の数は、日常的な直感を遥かに超える巨大さ

ZFC独立性と今後の展望

  • BB(6) の劇的な下限値向上により、 BB(n) の値が ZFC公理系 から独立になるnの値について再考
  • これまではn=20や30以降と考えられていたが、 n=7,8,9 あたりで既に独立となる可能性を示唆
  • 現在分かっているのは、 n=643 で独立となる事実

著者の個人的な近況とSTOC 2025

  • STOC 2025 (プラハ)に参加し、旧友との再会や新たな知見を得る体験
  • 自身の STOC基調講演「The Status of Quantum Speedups」 のスライドも公開
  • 世界情勢への不安を、研究や学術的な交流が和らげてくれる実感

コメントポリシーとブログ運営

  • 2024年7月 以降、コメントは原則として 著者(Scott Aaronson)への個人的なメッセージ として扱う方針に変更

  • 興味深い内容や議論を前進させるコメントのみ、 編集部の判断でブログに掲載

  • 掲載されない場合も、インターネット上で自由に発信可能であることを強調

    • コメントは HTMLやTeX記法 ($$ $$や( ))にも対応

Hackerたちの意見

だから、こう言ったんだ。「もし君が10,000,000sub10粒の砂を持っていたら、どうなるか想像してみて。そしたら…えっと…その砂で観測可能な宇宙の約10,000,000sub10コピーを埋められるんだ。」この部分がよくわからないんだけど、観測可能な宇宙の体積を砂の粒の平均体積で割ってるってこと?それって宇宙の質量よりもずっと桁が多い比較だよね。

そうだね、それは普通の数の桁数の範囲内だよ。10,000,000^10,000,000ですら、もうすごく大きくて、気にする必要ないし、ましてやその指数を9回も上げたら、もっと大きくなるし。

テトレーションを使うと、もう桁数の話じゃなくて、桁数の桁数の話になるんだ。

その通り。この数は10^100000とか、どれだけの砂の粒が入るかよりも、はるかに大きいから、その量で割っても本当に変わらないんだ。9,999,999sub10に近づくほどには、全然足りないよ。

そうだね、その比率で割ることは、実際にはその数にほとんど影響を与えない。むしろ、その表記法で「隣接」する数の方がずっと大きな変化をもたらす。10↑↑10,000,000 / (宇宙あたりの砂の粒数)は、例えば10↑↑9,999,999よりもずっと大きい。だから、これらの数を書くために使っているシステムでは、(非常に大きい)/(ただ単に大きい)を正確に書く以外に、もっと良い方法はないんだ。そして、非常に大きいの表記では、ほぼ(非常に大きい)に丸められるんだ。

こういう比較のもっと一般的な例を挙げると、重要な桁数では、10億から100万を引くと10億になるよ。

可視宇宙って、BB(6)の正確な値を書き下すのに十分な大きさなんだろうか。

そうじゃないよ。

確実にそうじゃないね。宇宙に保存できる情報量は約10^120ビットくらいだよ。たとえ桁数がトリリオンもずれてても、関係ないし。

観測可能な宇宙を閉じたシステムとして扱うなら、ベケンシュタインの限界を適用しようとすることができるかも。- R ≈ 465億光年(観測可能な宇宙の半径) - E ≈ 観測可能な宇宙の総質量エネルギー含む質量エネルギーは通常の物質、暗黒物質、暗黒エネルギーを含む。現在の推定では、観測可能な宇宙には約10^53 kgの質量エネルギー相当が含まれているとされている。これをS ≤ 2πER/ℏcに代入すると、最大情報量は約10^120ビットになる。 S ≤ 2πER/ℏc S ≤ (2 × 3.141593 × 3.036e+71 × 4.399e+26)/(1.055e-34 × 299792458) S ≤ 2.654135e+124 S ≤ 10^120 だから、ノー。

記事の最初の数は¹⁵10だよ。それは10^(¹⁴10)ってこと。つまり、¹⁴10桁あるってことだ。だから、無理だね。

あなたが言ってるのは、完全な表現のすべての部分が同時に存在する状態のことだと思う。もし同時に存在する必要がないなら、宇宙が無限の時間を持っているなら「書き下ろす」ことができるかもしれない(「かもしれない」と言うのは、熱的死がどう関わるか分からないから)。でも、「同時に」というのは相対論的な時空ではあまり明確じゃないよね。兄弟コメントは、CMBによって示される参照フレームに関しては確かに正しいと思う。でも、実際にある参照フレームで「同時に」表現できるように時空を切り取ることができるんじゃないかって考えてるんだ。

Hacker Newsで議論の続きを見る