ハクソク

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

なぜ忙しいビーバーのハンターは「アンチハイドラ」を恐れるのか

210日前原文(benbrubaker.com)

概要

  • 2024年夏、オンラインコミュニティが理論計算機科学の難問「ビジービーバーゲーム」でBB(5)の値を初めて特定
  • BB(5)は47,176,870で、単純なプログラムが実行できる最も複雑な計算の指標
  • 次の目標はBB(6)だが、「Antihydra」というプログラムの挙動解明が壁
  • Antihydraの問題はCollatz予想と類似し、未解決
  • 本記事ではAntihydra、Collatz予想、その関係性と難しさを詳述

ビジービーバー問題のブレイクスルーとAntihydraの壁

  • 2024年、 オンラインコミュニティ がビジービーバー数BB(5)の正確な値を特定
  • BB(5)は 47,176,870 で、約50年ぶりの大きな進展
  • ビジービーバー数は、 単純なTuring machine がどれだけ複雑な計算を実行できるかを測る指標
  • BB(6)の特定が次の目標だが、 Antihydra と呼ばれるTuring machineの挙動が未解明
  • Antihydra問題は、数学の未解決問題 Collatz予想 に似た構造

ビジービーバーゲームの基本

  • Turing machineの 状態数（ルール数） を「プログラムの複雑さ」として評価
  • 各Turing machineは、 0と1のテープ 上でルールに従い動作
  • 「最も複雑な計算」とは、 停止するまでに最も多くのステップ を要するマシン
  • BB(n)は「n状態のTuring machineのうち、停止するまでの最大ステップ数」
  • 実際には、 停止するかどうかの判定 が極めて困難

BB(6)の難しさとAntihydra

  • 6状態Turing machineの大半は 停止/非停止が判明済み
  • しかし、 1,618個の未判定マシン が残存
  • Antihydraはその中でも特に難解な 未判定マシン
  • BB(6)特定にはAntihydraの 停止性の解明 が不可欠
  • 現在の数学的手法では 解析不能

AntihydraとCollatz予想の関係

  • 多くのTuring machineは 高レベルな振る舞い で記述可能
  • 例：BB(5)は「xを3で割り、余りに応じて式を変えて繰り返す」高レベルプログラム
  • このタイプは Collatz-like（コラッツ型） と呼ばれる
  • Collatz予想：任意の正整数xに対し、「偶数ならx/2、奇数なら3x+1」を繰り返すと必ず1に到達するか
  • Antihydraの振る舞いは Collatz予想に極めて類似 し、停止性の証明が困難

Collatz型Turing machineの特徴

  • ある値xに対し、「Nで割った余りで次の式を決定し、特定条件で停止」
  • Collatz予想も「2で割った余りで分岐し、1で停止」
  • Collatz予想は すべての正整数で未解決
  • Antihydraの停止性も 同様の難しさ

ビジービーバー研究の今後

  • BB(5)の特定は 大きな進展
  • BB(6)の特定には Antihydraの停止性解明 が必須
  • Antihydra問題は、 純粋数学の未解決問題 に直結
  • 現状、 新たな理論的ブレイクスルー がない限り、BB(6)の特定は困難
  • ビジービーバー問題は、 計算理論・数学の限界 を示す好例

Collatz予想とAntihydraの本質的な難しさ

  • Collatz予想は「単純なルール」だが、 証明も反例も見つかっていない
  • Antihydraの解析も 同様に困難
  • 一見単純なTuring machineでも、 高レベルな数学的問題 を内包
  • BB(n)の値決定は、 計算可能性・停止問題の限界 を体現
  • この分野の研究は、 理論計算機科学と純粋数学の最前線

Hackerたちの意見

TLDR; BB(n)が大きくなるにつれて、ランダムウォークの位置に関連する停止条件を持つ問題をより多くエンコードできるようになるんだ。そんな条件が起こる可能性が低いことを証明するのは簡単かもしれないけど、絶対に起こらないことを証明するのはすごく難しい。

└

ただの非常に難しいことよりもずっとひどい: - 「コラッツ予想には絶対に近づくな！」（数学オタク） https://www.youtube.com/watch?v=TxBRcwkRjmc - 「経験豊富な数学者たちは、若手にコラッツ予想から離れるよう警告している。それは誘いの歌のようなもので、トランスにかかると二度と意味のある仕事ができなくなるかもしれない。」 https://www.quantamagazine.org/mathematician-proves-huge-res... - 「数学はまだそのような問題（コラッツのような）に対処する準備ができていない。」（ポール・エルデシュ）

「誰が大きな数を名付けられるか？」というスコット・アーロンソンの本から、なぜ私たちがビジービーバー数にこだわるのか: さあ、もしN番目のビジービーバー数、つまりBB(N)を知っていたら、Nルールのチューリングマシンが空白のテープで停止するかどうかを決められるんだ。マシンを実行するだけでいい。もし停止したらそれでOK。でも、BB(N)ステップ以内に停止しなかったら、もう絶対に停止しないってわかる。だってBB(N)は停止する前にできる最大のステップ数だから。同じように、もし全ての人間が200歳前に死ぬことがわかっていたら、サリーが200歳まで生きたら、彼女が不死であると結論できるよね。だから、どのチューリングマシンもビジービーバー数を列挙することはできないんだ。もしできたら、ハルティング問題を解決できることになって、それは不可能だってわかってるから。でも、面白い事実があるよ。もしN番目のビジービーバー数BB(N)よりも大きな数を名付けられたら、その数をDと呼ぼう。ビーバーダムのように、下のビジービーバーを守る屋根みたいなものだから。Dがあれば、BB(N)を計算するのは簡単になる。Nルールの全てのチューリングマシンをシミュレーションするだけでいい。Dステップ以内に停止しなかったマシン、つまりダムの屋根を突き破ったやつは、もう絶対に停止しないから。だから、どのマシンが停止するかを正確にリストできるし、その中でどのマシンも停止する前にかかる最大のステップ数がBB(N)なんだ。結論？ビジービーバー数列、BB(1)、BB(2)などは、計算可能な数列よりも早く成長する。指数関数や重ね合わせた指数関数、アッカーマン数列よりも早い。もしチューリングマシンがビジービーバーよりも早く成長する数列を計算できたら、その数列を使ってDを得られる。つまり、ビジービーバー数をリストできることになるけど、それは不可能だってわかってるよね。ビジービーバー数列は計算不可能なんだ、ただ単にすごく早く成長するから。どんなコンピュータでも追いつけないくらいにね。

└

うん、これをかなり前に読んだんだけど、その時の理由に何か引っかかるものがあって、今も気になってる。要するに、私の読みでは、その議論は計算可能な関数がBB(N)よりも速く成長することを否定していないけど、与えられた計算可能な関数がBB(N)より速く成長するかどうかを証明したり「決定」したりすることが不可能であることを示していると思う。これって結論と同じことなのかな？何か明らかなことを見落としてる？（それはありそうだね。スコット・アーロンソンは私よりずっと得意だし。）分かりやすくするために編集したよ。

BB(5)に関する報道がたくさんあったけど、1993年の同等の高レベルな定式化を伝えている人を見たことがなかったから、すごくクールだね！編集: 楽しみでRustに変換してみたら、数百万の数字がターミナルに出てくると思ったけど、実際にはこのループは15ステップで終了したのが面白い。チューリングマシンは4700万ステップかかるのにね。let mut x = 0; loop { x = match x % 3 { 0 => 5 * x + 18, 1 => 5 * x + 22, _ => break } / 3; } OEISのリンク: https://oeis.org/A386909 編集2: もちろん、この記事は次の段落でこれについて言及しているから、すぐにオタクにやられたってことだね。

└

これは、あなたのRustプログラムが数をバイナリで表現しているのに対して、BB(5)のチャンピオンであるチューリングマシンがユニタリーで表現しているからだよ。ユニタリーの算術は、桁数を使った算術よりも指数関数的に遅いから、後者を発明した理由なんだ。（チューリングマシンには他にも非効率な点があるけど、これが大きな概念的な違いだね。）

これってSETI@homeやビットコイン、AIのコード生成みたいなもの？昔はただ木を切って燃やして暖を取ってたんだ。それから座ってスポーツの試合をテレビで見て時間を無駄にしてた。

└

いや、これは分散コンピューティングの話じゃないよ。生の計算能力がボトルネックってわけじゃないからね。（それは、扱いやすいけど非自明なステップ数で停止する多くのマシンをチェックする必要がある場合にだけ役立つ。問題の超指数的な性質を考えると、それは狭い範囲で、興味のあるマシンはほとんどそこにいないと考えられている。）むしろ、これは人間（主にアマチュア）の数学者たちが問題の異なる部分を少しずつ解決していくコラボレーションなんだ。

└

スポーツボール この言葉を使う人は、一生ネットから追放されるべきだよ。

誰か他に読み込めない人いる？[0] [0] https://web.archive.org/web/20251027173129/https://benbrubak...

本当に良く書かれた記事だった。チューリングマシンを聞いたことがない人でも、BB(5)やBB(6)が何で、アンチハイドラがどう機能するか、そしてその数学的・歴史的な文脈を大まかに理解できたと思う。これは難しいことだから、よくやったね！

アンチハイドラは次の条件で停止する: シーケンスが1/2のモジュロの分布において（本当に/かなり）ランダムである場合。無限にフリップされた公正なコインでも、時には任意の長さの表または裏の結果が出ることがある。だから、問題はアンチハイドラのシーケンスが「十分に」ランダムかどうかってことだね。

└

本当にランダムなシーケンスがこのルールの下で必ず停止するとは思わないな。無限に長いランがあってもそれだけじゃ足りない。全体のシーケンスが大きくなるにつれて、終わらせるために必要なランの長さも長くなるから、確率は小さくなる。結果は有限の和を持つ幾何級数みたいな感じになるはずだよ。もっとシンプルな例を考えてみて。コインを3回、次に4回、5回と投げて、あるターンで全て同じ面が出たら停止するっていうやつ。停止する確率は1/4 + 1/8 + 1/16 + ...で、50%になる。これを永遠に続けると、最終的には10兆回の表か裏のランを見ることになるけど、10兆回目のターンの前にそのランを見ることはないだろうね。だから、質問は、アンチハイドラのシーケンスがランダム性から十分に逸脱することがあるのか、ってことだと思う。

└

定義上、ランダムではないよ。アンチハイドラは固定された計算可能なマップによって生成されるから、圧縮可能で、いくつかの有効な統計テストには合格しないんだ。決定論的アルゴリズムを使って真のランダム性は得られないし、計算可能な無限シーケンスはマーチン＝ロフのランダム性に失敗するんだ。ただ、経験的には、現在のすべての分析において、アンチハイドラの偶奇性は長いスパンで見ると大体公平に振る舞う（証明された奇数または偶数のバイアスはない）し、短期的な統計は擬似ランダムに見える。非停止は圧倒的にあり得そうだけど、具体的な証明は手の届かないところにあるみたい。

└

偶数/奇数のピークランの長さは「無限」に達するはずだけど、これらのランは全体の平均の中でどんどん小さな要素になっていくから、結局は長期的に見て50%に近づくと予想されるんだ。つまり、偏りのないランダムウォークはほぼ確実に原点に戻るけど、偏ったランダムウォークは非ゼロの確率で原点に戻れないってこと。これは偏ったランダムウォークと考えられるね[0]。だって、停止条件が50/50の期待値からどんどん離れていくから。

BB(6)の現在の最良の下限は2↑↑2↑↑2↑↑9だよ（これが意味不明なら「クヌースの上矢印」をググってみて）。この数字は信じられないほど大きくて、ちょっと気持ち悪くなる。特に、BB(5)からBB(6)に移ると、実際のビジービーバーTMを宇宙の寿命内でステップバイステップでシミュレーションできなくなるラインを越えたってことなんだ（宇宙の寿命のグーゴル倍でも同様）。この関数がどれだけ速く成長するか、本当に頭が混乱するよね。

└

この関数がどれだけ速く成長するか、本当に頭が混乱するよね。BB関数は明らかに整数の上で定義された関数だけど、質的に異なるアイテム（石、トースター、機械式時計、コンピュータなど）に対する関数として考えると役立つと思う。重要なアイデアは、基盤となる計算デバイスを「前のものより少し強力」ではなく、根本的に異なる種類の存在として見ることなんだ。

└

この関数の興味深い点の一つは、BB(748)を計算することがZFCに依存しないってことだよ。 https://scottaaronson.blog/?p=4916

└

BB関数は本当に驚くほど速く成長するよ。2↑↑2↑↑2↑↑9ステップで動くマシンは、4^12*23836540 = 399910780272640通りの異なる挙動をする6状態マシンのうちの1つなんだ[1]。同じように速く成長する関数には、機能的ビジービーバーがあるよ[3]。77519927606個の閉じたラムダ項の中で、サイズは https://oeis.org/A107668 [2] https://oeis.org/A333479 [3] https://en.wikipedia.org/wiki/Graham%27s_number

└

現在の最良の下限 じゃあ、現在の最良の上限はあるの？それとも「明らかに」分かるものはある？