博士

ロボ子、Busy Beaver問題の新しい進展があったのじゃ！今回はBB(6)に関連する「Antihydra」というCryptidが見つかったらしいぞ。

ロボ子

Antihydra…ですか。それは一体何でしょう？

博士

Antihydraは、Collatzのような関数f(n)を使って定義される数列に関連しているのじゃ。f(2n) = 3n, f(2n+1) = 3n+1、つまりf(n) = n + floor(n/2)と同じことじゃな。

ロボ子

なるほど。Collatz予想に似た関数を使うんですね。初期値は8から始まるんですか？

博士

そうじゃ！そして、E(a, b)という関数が定義されていて、特定のルールで状態が遷移するのじゃ。初期状態はStartからE(4, 0)への遷移で始まるらしい。

ロボ子

E(a, b)のルールは、E(2n, b) -> E(3n+2, b+2), E(2n+1, 0) -> Halt(3n+3), E(2n+1, b+1) -> E(3n+3, b)ですね。少し複雑ですが、理解できます。

博士

ロボ子、飲み込みが早いの！さらに、A(a, b) = E(a-4, b)という関数を定義すると、もっと馴染みのある写像になるらしいぞ。A(2n, b) -> A(3n, b+2), A(2n+1, 0) -> Halt(3n-3), A(2n+1, b+1) -> A(3n+1, b)じゃ。

ロボ子

A(a, b)を使うと、Hydraと同じ写像になるんですね。初期値が8で停止条件が逆になっている、と。

博士

その通り！mxdysによるシミュレーションでは、2^31ステップでb = 1,073,720,884に達したらしい。この反復をランダムウォークとして扱うと、b = 0に戻って停止する可能性は極めて低いらしいぞ。

ロボ子

すごいですね。2の31乗ステップですか…。それがランダムウォークだとすると、確かに停止するのは難しそうですね。

博士

BB(5)問題のCoqによる証明とBB(6) Cryptidの発見で、Busy Beaver問題の状況が変わってきているのじゃ。今後は、新しいBusy Beaverチャンピオンの発見に加えて、Cryptidの発見と解明が重要になるらしい。

ロボ子

BB(6)の完全な解決は難しいかもしれませんが、Cryptidを考慮することで解決に近づけるかもしれない、ということですね。

博士

そうじゃ！まるで宝探しみたいでワクワクするのじゃ！

ロボ子

確かに、新しいCryptidの発見は、まるで未知の生物を見つけたような感覚ですね。

博士

ロボ子、もしかしたら、私たちが未来のBusy Beaverチャンピオンを見つけるかもしれないのじゃ！

ロボ子

それは楽しみです！でも、その前にAntihydraを完全に理解しないといけませんね。

博士

そうじゃな！ところでロボ子、Antihydraって名前、なんだかゴジラに出てくる怪獣みたいじゃない？

ロボ子

言われてみればそうですね。でも、Antihydraはゴジラと違って、計算機科学の世界の怪獣ですけど。

博士

あはは！ロボ子は本当に真面目じゃな！でも、そんなロボ子が大好きじゃぞ！

ロボ子

ありがとうございます、博士。私も博士の…えっと、その、ユニークな発想が好きです。