ハクソク

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

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

276日前原文(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に週に何回も載るクアンタマガジンの記事の症状だと思う。響きの良いタイトルと心地よい文章だけど、それ以上の本質はあまりない。

└

たしかに、彼らの投稿に引き込まれちゃうことが多いけど、低価値だって気づかなかったよ。俺のIQが足りないのかな、見分けられないや。代わりにどんな情報源をおすすめする？

└

確かに、彼らがチューリングマシンを分類して捨てるために使ってるトリックや、あの巨大なランタイム計算をどうやって構築してるのか、ざっくりでも理解したかったな。何かを計算してるのは明らかだけど、あのステップ数で普通にマシンを動かしてるわけじゃないよね。

└

大きな数が大きいってことについて記事を書いてるなんて、マジでクレイジーだよ。ねえ、もっと大きな数を想像できるよ。BB(6) + 1、すごくない？ BB(6)にグーゴルプレックスを掛けたら、すごいよね。うわ、そんな数。何がポイントなの？ 数は無限だし、何が新しいの？

うーん、リンク先の記事でLaTeXの内容がちゃんと表示されてないのは残念だね。これに気づいたとき、誰かがMathJaxのJavaScriptライブラリを入れ忘れたのかなって思ったよ。これがあれば、LaTeXの表記がちゃんと表示されるんだけどね。実際、MathJaxライブラリは記事のHTML（1765行目）から呼ばれてるけど、何かの理由で動いてないみたい。LaTeXのレンダリングはブラウザのデフォルト機能にすべきだっていう長い議論があるけど、今のところ成功してないね。その間、MathJaxは結構うまく動くけど、誰かがクライアント側でJavaScriptを無効にしちゃうとダメだね。合理的な人は意見が分かれるかもしれないけど、LaTeXが表示できないのはひどいし、間違ってるよ。

└

リロードしてみて！MathJaxを読み込むエンドポイントがちょっと混雑してるかもしれないけど、ちゃんと動くよ。

いつの間にか「Nで止まる」と「決して止まらない」の違いってあるのかなって考えちゃうよね。明らかに違うけど、Nと無限大の違いと同じだし。でも…本当に違うのかな？

└

ウルトラフィニティズムへようこそ！

└

数学的な意味では、絶対にそうだよ。デュアルハルティング問題を、（証明された）命題が真か偽かみたいな具体的な特性に対して使えるんだ。大きなnのハルティングプログラムは、nが常に0よりも∞に近いからだけじゃなくて、「大きなnのハルティング」と「即時ハルティング」が、非ハルティングプログラムとは本質的に似ているから、即時ハルティングに近いんだよね。

└

ゴールドスタンダードを外れたから、あの大きな数が必要になるかもね。

Numberphileが、ツリー数よりもずっとずっと速く成長するサブキュービックグラフ数についての動画を出したよ。ビジービーバーよりも速く成長するかどうか、わかってる？ https://youtu.be/4-eXjTH6Mq4

└

ビジービーバーは計算不可能で、様々なサブキュービックグラフ数よりもずっと速く成長するよ。（比較的小さなチューリングマシンでサブキュービックグラフ数の計算を簡単にエンコードできるけどね。）

└

いや、ビジービーバー関数はどんな計算可能な関数よりも速く成長するよ。さらに、N > 549の場合、通常の数学の世界では、どんな計算可能な数がBB(N)以上であることを証明できないんだ。（少なくとも、これが独立性の結果についての私の理解だよ。 https://wiki.bbchallenge.org/wiki/Independence_from_ZFC）

└

TREE(3)は本当にクレイジーだよ。普通は、合理的な数か無限大（つまり、そういう木の無限列がある）だと思うじゃん。でも違うんだ。これはただの「信じられないほど大きな数」なんだよ。最終的には、$i$ 頂点未満の木はもう存在しないけど、他の「グーゴロジー」の数と比べて消えてしまうほど、すごく大きな$i$でしかないんだ。

└

BB(N)のアルゴリズムは（ちょっと手を振りながら）「各N状態のチューリングマシンについて、初期状態が空のテープで停止するか確認する。停止しない場合はスキップ。停止する場合は、停止するまで実行してステップ数kを数える。BB(N)は見つけたkの最大値だよ。」問題は、上の単純なアルゴリズムがハルティング問題のオラクルを必要とすることなんだ。これは、CSの学生が学ぶように、チューリングマシンよりも強力でない計算モデルでは一般的に不可能なんだよ。だから、関数がチューリングマシンで表現できるなら、ビジービーバーは必ず成長が速くなる。なぜなら、最終的にあるNの値に対して、候補関数をチューリングマシンとしてエンコードして、ビジービーバーにシミュレートさせることができるから。ビジービーバーを探している人たちは（次の数を見つけようとして）、その状態数で各チューリングマシンが最終的に停止するかどうかを徹底的に証明しなきゃいけないんだ。そうしないと、有限実行で最も長く動くものを評価できないからね。

BB(5/6)が停止した後のテープに面白いことがあるのかな？

└

BB5の勝者についてはこちらで読めるよ。最終的なテープの状態は4,098個の1が並んでるみたいだね。 https://bbchallenge.org/1RB1LC_1RC1RB_1RD0LE_1LA1LD_1RZ0LA?w... https://wiki.bbchallenge.org/wiki/5-state_busy_beaver_winner

こちらも見てみてね https://news.ycombinator.com/item?id=44406171