BusyBeaver(6) は本当に巨大

 (scottaaronson.blog)
2 ポイント 投稿者 GN⁺ 2025-06-29 | 1件のコメント | WhatsAppで共有
  • Busy Beaver の6番目の値（BB(6)） の下限が、最近の新たな研究によって大幅に引き上げられた
  • 従来は BB(6) > 10↑36,534 とされていたが、2022年に BB(6) > 10↑1510 へ上方修正された
  • 最近では BBchallenge で BB(6) > 10↑10,000,00010 に再び引き上げられ、さらに 2 ↑↑ (2 ↑↑ (2 ↑↑ 9)) まで更新された
  • BB(6) の大きさは想像を絶しており、この数は宇宙全体を何度も埋め尽くせるほどである
  • こうした進展は、数理論理と計算理論 の限界と可能性を新たに認識させる契機となっている

BB(6) 最近の研究成果の概要

  • ここ数年、世の中や研究環境が厳しく感じられる状況が続いていた
  • しかし今回の Busy Beaver 研究の進展は、研究に対する純粋な情熱を改めて思い出させるきっかけとなった
  • 2022年には Pavel Kropitz が BB(6) > 10↑1510 であることを証明した
    • BB(6) は、6状態を持つチューリングマシンがオールゼロのテープ上で停止するまでに最大何回動作できるかを意味する
    • ここで ^1510 は、10 を自分自身で 15 回繰り返し冪乗した値（テトレーション）である
  • それ以前の研究では BB(5) が 47,176,870 であることが明らかになっており（BBchallenge チーム）、これはこの値が観測可能な現実の範囲を超える領域へ急増し始める地点である

最近の下限更新の過程

  • BBchallenge の "mxdys" が BB(6) > 10↑10,000,00010 であることを証明した
    • この証明は Coq 言語で書かれた形式的証明に基づいている
  • その後さらに BB(6) > 2 ↑↑ (2 ↑↑ (2 ↑↑ 9)) へと下限が更新された
    • ↑↑ はテトレーション（冪乗の反復）を意味し、これは 2 を 2 でテトレーションし、さらにその結果を使ってテトレーションを 9 回繰り返す形である
    • これほどの数は、既存のどの直感的理解をも超越する領域に属する
  • 参考までに、ペンテーションはテトレーションの反復を意味し、この種の演算は乗算、冪乗、テトレーションを超える演算である

巨大数の大きさを理解する

  • 記者からの依頼で、10↑10,000,00010 という数の大きさを説明する必要があった
  • この砂粒の個数は、10↑10,000,00010 個の宇宙を砂で満たせるほどである
  • このように、BB(6) の値が実際に観測できる世界をはるかに超えていることが伝えられている

BB アルゴリズムの本質的限界についての考察

  • BB(6) の途方もない大きさは、Busy Beaver 関数の真の潜在力を示している
  • BB(n) の値が集合論（ZFC）の公理系から独立になる時点は n=20〜30 程度と推定されていたが、おそらく n=7〜9 でもすでに独立になり得ることを予想させる
    • 現在は n=643 で独立であることが公式に知られている

付録: 最近のイベントと講演の知らせ

  • 筆者は最近プラハで開かれた STOC'2025 のイベントに参加し、さまざまな研究者と交流して新しい情報を得た
  • 自身の 量子高速化の現状 に関する基調講演スライドも共有した
  • この内容についてのより詳しい感想は後日共有する予定である

関連記事

1件のコメント

 
GN⁺ 2025-06-29
Hacker Newsのコメント
  • bbchallenge Discordサーバーで、Graham's Numberを超えるにはチューリングマシンの状態数がどれくらい必要かを人々が推測している様子が共有されている。最近のBB(6)の勝者が達成した 2^^2^^2^^9 もすでに途方もない数だが、Grahamのような成長の仕方が思ったより早く現れうることに驚いている。49ビットのラムダ項だけでも十分だという functional busy beaver [1] の資料と、そのサイズの閉ラムダ項がわずか77519927606個しかない[2]一方で、6-stateチューリングマシンは実に399910780272640個も存在する[3]ことに触れている。ペンテーションがたった6状態で実装されたことを受け、関係者のかなり多くが、7状態ならGraham's Numberも超えられると考える雰囲気になっているとも述べている。それでも本人としては依然として意外だと感じている。数日前、今後10年以内にBB(7)がGraham's Numberを超えるという証明が出るかどうかで大きな賭けをしたと紹介し、他の人の意見を尋ねている。(1, 2, 3 リンクあり)
    • 専門家ぶるつもりはないが、BB(7)はGraham's Numberより大きいと予想する。BBは任意の計算可能な数列より速く成長しなければならないので、実際のBB(7)がどれほど大きいかは手探りでしかないが、最終的にはすべての計算可能な演算子（たとえば up-arrow^n など）よりも速く成長する方向にあるはずだ。47176870から 2^^2^^2^^9 への成長幅は、2^^2^^2^^9 からGraham's Numberへの幅よりも、演算子の強さという意味ではるかに劇的な変化だという感覚がある。Graham's Numberは g_64 で、これも up-arrow^n より一段上の概念として解釈できるので、BB(7)はGraham's Numberを超えるだろうという直感を共有している。
  • BB(748)のように、非計算的な数がZFC（集合論の公理系）から独立であるという事実は非常に不思議だと述べている。まるでカテゴリーミスのように感じるという率直な感想を共有している。
    • BB(748)がZFCから独立である理由は、その値そのものではなく、748状態のうちの1つである TM_ZFC_INC が、ZFCの中で矛盾（偽の証明）が見つかったときにだけ停止する仕組みだからだ。BB(748)=N を証明するには、TM_ZFC_INC が N ステップ以内に停止するか、あるいは無限に走り続けることを示す必要があるが、ゲーデルの不完全性定理によれば、ZFCに矛盾がないならそのどちらも証明できないことになる。
    • 少ない行数のテキスト、つまりZFCの公理そのものが、人間にとって重要な算術的真理を十分に表現できると考えたこと自体のほうが、もっと驚くべきことだと感じる。6状態チューリングマシンの振る舞いですら簡単には予測できない現実は当然だ。ゲーデルの不完全性定理の発表後、数学界はより多くの公理を探しにかなり積極的に動くべきだったのに、実際には基礎研究の一部でしか扱われなかったことへの残念さを述べている。
    • 連続体仮説の真理値（プラトニズム的に見れば1か0か）は、ZFCから独立であることが証明されている良い例だ。巨大な数どころか、単なる1ビットすらZFCでは保証できない。
    • BB(n)が非計算的であることと、BB(748)は（定義上）748状態チューリングマシンが書いた1の個数なので計算可能な数であることを明確に区別している。「独立的」というラベル自体は、ZFCだけではこの数が本当に我々の求める値であることを証明できず、より強い理論が必要だという話だと説明している。
    • 数字そのものがZFCから独立しているのではなく、BB(748)を計算する過程が独立的なのだと強調している。（すべての整数はZFCで表現可能）
  • BB(14)がGraham's Numberより大きいことはよく知られており、今回の研究でBB(7)もGraham's Number以上になるだろうという直感を述べている。直観的には、ペンテーションからGraham's Numberに至るアイデアのほうが、47,176,870から 2 <pentate> 5 に到達するよりむしろ単純に感じられる。
    • 良い情報だとして、自分の投稿へのすばらしい返信になりそうだと反応している
  • Scott Aaronson の “How Much Math Is Knowable?” [Harward CMSA] のYouTube講演 https://www.youtube.com/watch?v=VplMHWSZf5c と、最近のHNでの議論 https://news.ycombinator.com/item?id=43776477 を共有している
  • 「左上の肩付き指数」はテトレーション、つまり反復べき乗だと説明している。¹⁵10 なら 10 の 10 の…を15回繰り返すという意味だ。初見では誤植かと思ったと共有している。
    • 反復演算という流れで、今度は「ペンテーション」を初めて知ったという反応
    • テトレーションは以前に見たことがあるが、Knuthのup-arrow記法[1]のほうがより一般的で、一般化にも向いているという好みを述べている（1）
  • BB(6)が、6状態2記号（{0,1}）チューリングマシンが初期0テープから停止するまでの最大ステップ数だという説明は、非専門家にとって非常に有益だった。この分野が何十年も研究してきた人向けの高密度で専門用語だらけの世界だと実感したが、偶然このように深い記事に触れられて興味深かったという前向きな感想を共有している
    • コンピュータサイエンスの学部生レベルなら、busy beaver問題を初めて見ても感覚はつかめる内容だと思う。もちろん特殊な用語は多いが、何十年もの経験者専用だと感じる必要はないという励ましめいた助言を加えている
    • この定義はソフトウェアエンジニアリングよりも、計算機科学理論の側で標準的なものだと述べている
  • 「10,000,000 sub10」個の砂粒があれば観測可能宇宙を 10,000,000 sub10 倍満たせるという説明に混乱したと述べている。観測可能宇宙の質量と比較するのが普通だが、このやり方だとすでに実際の物質量をはるかに超えていると指摘している
    • その通りだと返答している。砂粒/宇宙で割ったとしても、それ自体がほぼ同程度の巨大数なので、この表記法での隣り合う数同士は桁違いに離れている。10↑↑10,000,000 / (砂粒/宇宙) も 10↑↑9,999,999 よりはるかに大きいと説明している。我々の体系では、（非常に大きい）/（宇宙的に大きい）も結局は（非常に大きい）のままだという比喩だ。
    • テトレーションでは、もはや単純な桁数の比較ではなく、「桁数の桁数」というレベルの成長だと補足している
    • この数は砂粒 10^100000 個程度で割ってもまったく小さくならないので、割り算の影響は本質的に無視できると再確認している
    • 10,000,000^10,000,000 ですら十分に途方もない大きさで、そこにもう一段指数の尾を足すと比較自体が無意味になるという例を挙げている
    • よくある例として、有効数字の考え方では 10億 - 100万 = 10億 と言っても大げさではないことを示している
  • 5状態チューリングマシンで証明列挙が可能な論理体系のうち、最も「豊かな」ものは何だろうと疑問を呈している
    • どんな基準で「列挙」を定義するかによって答えは変わりうる。関連する問いとして、「5状態チューリングマシンの停止性をすべて証明できない最強の論理体系は何か？」というものも意味がある。Skelet #17 [0] が停止しないことを数学的に証明するのは非常に難しいので、これを証明できる理論があれば、残りの5状態チューリングマシンもすべて決定できるのではないかという個人的見解を共有している（0, 1）
    • 有限の二進文字列を論理的証明の列挙としてどう解釈するかを明確にしてはじめて、前提を議論できる
  • 観測可能宇宙はBB(6)の正確な値を書き留めるのに十分な大きさだろうか、という疑問が出ている
    • 観測可能宇宙を閉じた系と見なした場合、Bekenstein bound を適用すると情報保存の上限は約 10^120 ビット程度になる。現在の推定では全質量エネルギーはおよそ 10^53kg で、これを式に入れてもやはり 10^120 ビット前後になる。したがって不可能だと数値的根拠とともに説明している
    • 宇宙に保存できる情報量は約 10^120 ビットであり、たとえ何桁も見積もりを間違えていたとしても意味がないほど「明らかに足りない」と強調している
    • 値全体を同時に保存する状況を仮定しているのだろうと推測している。同時性を要件にしないなら、無限の時間をかけて理論上は記録できるかもしれないが、宇宙の熱的死など現実的な限界を考える必要がある。CMB基準のフレームでは不可能だが、別の時空の切り方を考えられるのではないかと自問している
    • 記事中の最初の数ですらすでに ¹⁵10、つまり 10^(¹⁴10) の形なので、桁数自体が ¹⁴10 であることを考えれば絶対に不可能だ
    • 不可能だと簡潔に再確認している
  • 計算複雑性理論のこうした結果を見るたびに、「スーパーAIは神だ」系の流行の言説は完全に根拠がないと実感する。宇宙のすべての原子をスーパーコンピュータに変え、ブラックホールのエネルギーまで使ったとしても、BB(6)の停止状態を計算することは永遠に不可能だ
    • そういう strawman は最初から説得力がなかったという簡潔な反応