BusyBeaver(6) は本当に巨大
(scottaaronson.blog)- BB(6) の既知の下限が再び大幅に引き上げられ、6状態チューリングマシンの最大停止時間が観測可能な現実の規模をはるかに超えることが確認された
- BB(6) は、0で埋められたテープから開始する 6状態・2記号チューリングマシン が停止前に実行できる最大ステップ数を意味する
- 2022年の Pavel Kropitz による改良以降、mxdys が下限を 10を1000万回反復べき乗した数 より大きい水準へとさらに引き上げた
- 最新の結果は、BB(6) が 2 pentated to 5 以上であることを示しており、反復べき乗よりさらに1段階上の演算が登場した
- BB(5) は 47,176,870 と確定している一方で、BB(6) は圧倒的に巨大であり、BB(n) が ZFC 公理系と独立になる地点が n=7, 8, 9 かもしれないという推測につながっている
BB(6) の下限が再び拡大
- 2022年以前は BB(6) について BB(6) > 10^36,534 程度しか知られておらず、Pavel Kropitz がこれを 10を15回反復べき乗した数 より大きい水準へと改善した
- テトレーション(tetration) は反復べき乗を意味する
- たとえば 10 を 15 回積み上げた数は、10 の 10 の 10 の … という形が 15 回続く数である
- BBchallenge の主催者 Tristan Sterin は、チームメンバーの mxdys が BB(6) の下限を再び引き上げたと知らせた
- 最初の改良: BB(6) > 10を1000万回反復べき乗した数
- この結果には Coq 正確性証明 がある
- mxdys のその後の改良は、BB(6) が 2 tetrated to 2 tetrated to 2 tetrated to 9 以上であることを示している
- とくに BB(6) は 2 pentated to 5 以上である
- ペンテーション(pentation) は反復テトレーションであり、テトレーションがべき乗を反復するのよりさらに1段階上の演算である
BB(5) と BB(6) の極端な差
- BB(6) は 6番目の Busy Beaver 数 である
- 6状態チューリングマシンを対象とする
- アルファベットは {0,1}
- 入力テープは最初はすべて 0
- 停止する前までに可能な最大実行ステップ数を意味する
- 国際的な BBchallenge チームは昨年、BB(5) を 47,176,870 と確定した
- BB(5) から BB(6) へ移るあいだに、Busy Beaver 関数は 数千万単位 から観測可能な現実の範囲を超える大きさへと跳躍した
大きさの感覚がほとんど通用しない数
- BB(6) > 10を1000万回反復べき乗した数であった時点でも、直感的な説明はほとんど不可能だった
- たとえば、それほどの砂粒があるなら、観測可能な宇宙の複製をだいたい同じ数だけ埋め尽くせる、とたとえられる
- このたとえは、その数が 10^100 のような宇宙的スケールの数よりもなお圧倒的に大きいため、割り算をしても元の数とほぼ同じ規模のまま残ることを示している
ZFC 独立性の推定が下がる可能性
- BB(6) がここまで大きくなったからといって、Busy Beaver 関数についてのあらゆる見方が変わったわけではない
- BB(6) が 10^36,534 のような比較的小さい水準ではなく、反復演算の領域 にある可能性はもともと開かれていた
- 実際の下限がそのような規模で確認されたことで、BB(n) の値が ZFC 集合論公理系 と独立になる地点についての推定が下がる可能性がある
- 以前なら n=20 や 30 付近を考えることもできた
- 今では n=7, 8, 9 かもしれないと見られている
- 現在知られている ZFC 独立性の結果は、BB(n) が n=643 で ZFC と独立になるという水準である
別途アップデート: STOC 2025
- STOC 2025 が開催された Prague で複数の研究者に会い、新しい内容に触れた
- STOC の plenary lecture のタイトルは The Status of Quantum Speedups である
- 関心のある読者は、その講演の PowerPoint slides を確認できる
1件のコメント
Hacker Newsのコメント
bbchallengeのDiscordサーバーでは、最新の BB(6) チャンピオンが達成した
2^^2^^2^^9よりはるかに大きい Graham's Number を超えるには、チューリングマシンの状態がいくつ必要なのか活発に推測されていますfunctional busy beaver https://oeis.org/A333479 を見ると、Graham級の挙動は意外に早く現れる可能性があります。49ビットのラムダ項で十分です
その大きさ以下の閉じたラムダ項は77,519,927,606個しかありませんが https://oeis.org/A114852、固有の6状態チューリングマシンは
4^12*23836540=399910780272640個あります https://oeis.org/A1076686状態だけでペンテーションを達成したので、今では7状態ならGraham's Numberを超えられると見る人が何人もいます。それでも私はまだかなり驚くべきことだと思っています。数日前、そのうちの一人と、今後10年以内に
BB(7)>Graham'sの証明が出るかどうかで大きな賭けをしたのですが、みんながどう見ているのか気になりますBBは、どんな計算可能な数列よりも速く増大しなければなりません。これがBB(7)について具体的に何を意味するかは、結局のところ身振り手振りの説明に近いですが、演算子の強さの階段を非常に速く上らなければならないという感覚です。最終的には、私たちが定義するどんな計算可能な演算子よりも速く増大しなければならず、例えば
up-arrow^nや、計算可能関数fに対するup-arrow^f(n)も含まれます直感的には、
47 millionから2^^2^^2^^9への成長のほうが、2^^2^^2^^9からGraham's Numberへの成長よりも、必要な演算子の強さという点で質的にずっと大きく見えます。Graham's Numberはg_64で、ここでgはおおよそup_arrow^nの一段上にあるものなので、おそらくBB(7)>Graham's Numberである可能性が高いでしょうBB(748) のような数、それも計算不能な数が「ZFCと独立」であり得るというのは頭がくらくらします。何かカテゴリーエラーのように感じます
TM_ZFC_INCがZFC内の矛盾、つまりFALSEの証明を探し、それを見つけたときだけ停止するようになっているためですしたがって
BB(748)=Nという証明は、TM_ZF_INCがNステップ以内に停止することを示すか、決して停止しないことを示さなければなりません。ZFCが無矛盾だと仮定すると、ゲーデルの有名な結果により、どちらも不可能ですnについてBB(n)の値を出力するアルゴリズムが存在しないという意味ですBB(748)は計算可能です。定義上、748個の状態を持つあるチューリングマシンが書き出す1の個数であり、そのマシンがBB(748)を計算します数そのものは、文字通り想像もできないほど大きな整数にすぎません。ZFC独立性は、この数が私たちの探しているその数だと証明しようとするときに入ってきます。そのためには、748状態チューリングマシンの性質を捉えられる、ZFCより強い理論が必要です
6状態チューリングマシンの挙動が数行のテキストでは予測不能になり得ることは、まったく驚きではありません
ゲーデルが第一不完全性定理を発表した直後に、数学界全体がより多くの公理を探すことへ全速力で走ったものだと思っていました。ところがほぼ1世紀にわたり、ゲーデルの仕事は主流のプログラムというより、基礎論の狭い領域にとどまる奇妙な事実のように扱われてきた面があります。FefermanやFriedmanらのことは知っていますが、この分野の研究は数学の他の大多数のテーマに比べてはるかに少ないです
BB(748)の値だと立証されるものは存在しませんしたがって、ZFCが
BB(748)の値を出力すると証明できるプログラムも存在しません。しかし他のすべての数と同じく、BB(748)を出力するプログラム自体は存在しますBB(14) がGraham's Numberより大きいことは知られていますが、今回の結果を見ると
BB(7)もおそらくGraham's Numberより大きそうです直感的には、ペンテーションからGraham's Numberへ進むのに必要な技術のほうが、
47,176,870から2 5へ進むのに必要な技術よりも単純に感じます左上付き文字がテトレーション、つまり反復累乗を意味するという説明を見て、最初はタイプミスかと思いました。テトレーションに初めて触れました「
10,000,000sub10個の砂粒があると想像してほしい。そうすると、観測可能な宇宙10,000,000sub10個ほどをその砂で満たせる」という部分が理解できない本当に観測可能な宇宙の体積を平均的な砂粒の体積で割った値を丸めて消しているのか？ それは通常比較に使われる宇宙の総質量よりも、桁数の差がはるかに大きい
10↑↑10,000,000 / (宇宙1個あたりの砂粒の数)は、たとえば10↑↑9,999,999よりも圧倒的に大きいこういう数を扱う体系では、
(非常に大きな数)/(宇宙規模にすぎない数)を正確にそう書く以外に、より良い表現はほとんどなく、非常に大きな数の側の表記では結局ほぼ(非常に大きな数)に丸められる10^100000や砂粒が何個入るかといった量よりもあまりに大きいので、それだけ割っても実質的には変わらない。少なくとも9,999,999sub10に近づくほど下がることはない10,000,000^10,000,000だけでもすでにその程度はどうでもよくなるほど大きいのに、まして指数そのものをさらに9回べき乗した後ならなおさらであるScott Aaronson の How Much Math Is Knowable? [Harward CMSA]: https://www.youtube.com/watch?v=VplMHWSZf5c
数か月前に HN にも上がっていた: https://news.ycombinator.com/item?id=43776477
5状態チューリングマシンだけで証明を列挙できる最も豊かな論理は何だろうか？
このバージョンについては少し考えてみたが、一階論理に関する専門性が足りず、あまり先には進めなかった。私の知る限りでは、Skelet #17 https://bbchallenge.org/1RB---_0LC1RE_0LD1LC_1RA1LB_0RB0RA は数学的に非停止を証明するのが最も難しい機械の一つなので https://arxiv.org/abs/2407.02426、Skelet #17 が停止しないことを証明できる理論なら、残りの5状態機械も判定できる可能性が高い
「BB(6) は6番目の Busy Beaver 数、つまり
{0,1}アルファベットを持つ6状態チューリングマシンが、最初はすべて0のテープ上で実行されるとき、停止するまでに取り得る最大ステップ数」という説明を見て、非専門家の自分にはむしろよく分かりすぎるように感じたこれは何十年もこうした研究をしてきた人たちのためのハードコアなブログであることは間違いない。特定の読者に向けて、遠慮なく密度高く専門用語だらけに書かれた記事に偶然出会うのは、なかなか素晴らしい
ニッチな専門用語であるのは確かだが、何十年も費やした人だけがアクセスできると考えるのは、自分を過小評価している
そんなに大きな数は人間には視覚化できない。数を表現する方法は、単に数えることだけではない
たとえば砂粒1つにも可能な状態が無限に多いと見なせる。実数は無限に多いので、砂粒1つが
BB(6)を表現できると言うこともできる。組み合わせは指数的に大きくなり得るので、そのような方法が表現に有用かもしれないつまり、ある体系がばれるまでどれだけうまく矛盾していないふりをできるか、という問題である。
BB(3)によって無矛盾性を装う矛盾した体系は、BB(6)によって無矛盾性を装う体系よりもはるかに早く「露見する」。ここで無矛盾性を装うとは、あるnについてBB(n)ステップより長く実行されるすべてのプログラムは停止しない、と主張することを意味する無限精度を持ち出して扱いやすそうに見せるのは、私の基準では手品に近い。規模を説明するときは整数を使うほうがよい
観測可能な宇宙が BB(6) の正確な値を書き記せるほど十分に大きいのか気になる
R ≈ 46.5 billion light-years、つまり観測可能な宇宙の半径を使い、E ≈観測可能な宇宙の総質量エネルギー含有量を使用する質量エネルギーには通常の物質、暗黒物質、暗黒エネルギーが含まれる。現在の推定では、観測可能な宇宙はおよそ
10^53 kgの質量エネルギー等価量を持つこれを
S ≤ 2πER/ℏcに代入すると、最大情報量はおよそ10^120 bits程度になるS ≤ 2πER/ℏcS ≤ (2 × 3.141593 × 3.036e+71 × 4.399e+26)/(1.055e-34 × 299792458)S ≤ 2.654135e+124S ≤ 10^120だから不可能
¹⁵10である。これは10^(¹⁴10)という意味で、したがって桁数は¹⁴10個ある。なので書き記すことはできないただし相対論的時空では「同時に」という言葉はうまく定義されない。兄弟コメントは、宇宙マイクロ波背景放射が示唆する基準系では確かに正しい。ただ、ある基準系では「同時に」表現できるように時空を切る方法があり得るのではないかと思っている