最も長く実行される単純なコンピュータプログラムを見つけるための探求

この物語 のオリジナル版はQuanta Magazineに掲載されました。

誰かがあなたに5つの数字のリストを渡したと想像してみてください。1、6、21、107、そして（ちょっと待ってください）47,176,870です。次に何が来るか分かりますか？

行き詰まっているのはあなただけではありません。これらは最初の5つのビジービーバー数です。これらは、理論計算機科学における最も難解な問題の一つと密接に結びついた数列を形成しています。ビジービーバー数の値を決定することは、60年以上にわたり、プロ数学者とアマチュア数学者の両方から熱狂的な支持を集めてきた、非常に困難な課題です。

研究者たちは1960年代と1970年代に、最初の4つのビジービーバー数を特定しました。BB(5)と呼ばれる、際立って大きい5番目の数は、昨年になってようやく「ビジービーバーチャレンジ」と呼ばれるオンラインコミュニティで活動するアマチュア数学者を中心としたチームによって決定されました。

BB(6)の大きさは誰にも分からない。私たちが知っているのは下限値だけであり、しかもそれは実に驚くべきものだ。2022年、忙しいビーバーハンターたちは、BB(6)は少なくとも、通常の十進法で書き表すことが文字通り不可能なほど大きいはずだと証明した。たとえ宇宙のあらゆる原子に何らかの方法で数字を刻み込んだとしても、測定可能な進歩を遂げる前に原子が尽きてしまうだろう。

「これは私たちが理解したり、手に入れたりできる範囲をはるかに超えたものだ」とテキサス大学オースティン校のコンピューター科学者、スコット・アーロンソン氏は語った。

多忙なビーバーハンターたちは、この驚くほど大きな数字がさらに大きいはずであることを発見した。この発見は、ビジービーバーチャレンジで最も謎めいて多作な貢献者の一人によるもので、彼は6月にBB(6)の新たな下限を証明し、わずか9日後に再び記録を更新した。この新たな結果は、2022年の下限が実に小さな数字に見えてしまうほどだ。

「驚きが止まりません」とメリーランド大学のコンピューター科学者、ウィリアム・ガサーチ氏は語った。「6という数字は、私たちを巨大な数字の成層圏へと導いてくれるのです。」

ビーバートラップ

ビジービーバー番号の背後にある、非常に難しい質問は次のとおりです。コンピューター プログラムのコードが与えられた場合、それが最終的に停止するか、永久に実行されるかを判断できますか。

1936年、先駆的な論理学者アラン・チューリングは、この問題に答える普遍的な手順は存在しないことを証明しました。これは停止問題として知られるようになりました。あるプログラムで有効な手法は、他のプログラムでは機能せず、場合によってはどの手法も機能しないことがあります。

チューリングはこの画期的な結果を、計算の形式的な数学モデルを発明することで証明しました。このモデルでは、プログラムは、現在チューリングマシンと呼ばれる仮想的な装置によって表現されます。各チューリングマシンは、単純な規則の一意のリストに従って、離散的なステップで計算を実行します。チューリングマシンの規則の数が増えるほど、その動作は複雑になり、停止するかどうかの判断が難しくなります。

しかし、どれほど難しいのでしょうか？1962年、数学者ティボール・ラドは、この問題を探求する新しい方法を考案しました。彼はこれを「ビジービーバーゲーム」と名付けました。このゲームでは、まず特定の数のルール（その数をnとします）を選びます。目標は、最終的に停止するまでに最も長く動作するnルールのチューリングマシンを見つけることです。このマシンはビジービーバーと呼ばれ、対応するビジービーバー数 BB( n ) は、そのマシンが実行するステップ数です。

原理的には、任意のnに対してビジービーバーを見つけたい場合、いくつかの手順を実行するだけで済みます。まず、n規則チューリングマシンの候補をすべてリストアップします。次に、コンピュータプログラムを使って各マシンの実行をシミュレートします。マシンが決して停止しない兆候を探します。例えば、多くのマシンは無限ループに陥ります。停止しないマシンはすべて破棄します。最後に、他のすべてのマシンが停止するまでに何ステップ実行したかを記録します。実行時間が最も長いマシンが、あなたのビジービーバーです。

実際には、これは難しくなります。まず、新しいルールが加わるたびに、考えられるマシンの数は急速に増加します。それらをすべて個別に分析するのは不可能なので、マシンを分類して除外するためのカスタムコンピュータプログラムを作成する必要があります。分類しやすいマシンもあります。すぐに停止するか、簡単に識別できる無限ループに陥ります。しかし、明確なパターンを示さずに長時間動作するマシンもあります。このようなマシンの場合、停止問題は恐ろしいほどの悪名を馳せるに値します。

ルールを追加すればするほど、必要な計算能力は増大します。しかし、力ずくで計算するだけでは不十分です。一部のマシンは停止するまでに非常に長い時間動作するため、段階的にシミュレーションすることは不可能です。実行時間を測定するには、巧妙な数学的トリックが必要です。

「技術の進歩は確かに役立っています」と、長年ビーバーハンターとして活躍するソフトウェアエンジニアのショーン・リゴッキ氏は言う。「しかし、効果は限られています」

時代の終わり

多忙なビーバーハンターたちは、BB(5)問題が行き詰まっていた1990年代から2000年代にかけて、BB(6)問題に本格的に取り組み始めた。その中には、応用数学者であるショーン・リゴッキと彼の父テリーがいた。彼らは、ローレンス・バークレー国立研究所の高性能コンピューターで、空き時間に探索プログラムを実行していた。2007年、彼らは6つのルールを持つチューリングマシンを発見し、実行時間の最長記録を破った。停止するまでに要したステップ数は約3,000桁だった。これは通常の基準から見ても途方もない数字だが、書き留めるには大きすぎるほどではない。12ポイントのフォントで書けば、3,000桁は紙1枚分に収まるほどだ。

3年後、スロバキア出身のコンピュータサイエンス学部生、パベル・クロピッツは、卒業論文としてBB(6)探索に取り組むことを決意した。彼は独自の探索プログラムを書き、大学の研究室にある30台のコンピューターネットワーク上でバックグラウンドで動作するように設定し、1ヶ月後、リゴツキ夫妻が発見したものよりもはるかに長時間動作するマシンを発見した。多忙なビーバーハンターたちの言葉で言えば、それは新たな「チャンピオン」だった。

「幸運でした。研究室の人たちがすでに私のCPU使用率について不満を言っていたので、少しスケールダウンする必要がありました」と、クロピッツ氏はBusy Beaver ChallengeのDiscordサーバーでのダイレクトメッセージのやり取りで述べた。さらに1ヶ月の探索の後、彼は自身の記録を破り、実行時間が3万桁を超えるマシンを開発した。これは約10ページ分に相当する。

クロピッツのマシンは12年間、BB(6)の記録を保持していました。2022年5月、ショーン・リゴッキは強力なコンピュータクラスターを利用できる新しい仕事に就き、古いコードを新しいハードウェアで実行してみることにしました。そして案の定、クロピッツの記録を破る新たなチャンピオンを発見しました。この発見は、その後の活発な動きのきっかけとなりました。2週間の間に2度、リゴッキは活発なビーバーのメーリングリストで新たなチャンピオンを発表しました。そのたびに、クロピッツは3日以内に彼の記録を破りました。リゴッキは、父親がクロピッツの偉業に驚嘆していたことを覚えています。

「彼はパベルがもうBB(6)を解いたと思っていると冗談を言っていました」とリゴツキは言った。「チャンピオンを見つけると、彼はいつもバッグから少し大きいものを取り出すんです。」

しかし、リゴッキ氏とクロピッツ氏が発見した最後の 2 台のマシンは、現チャンピオンより少し長く動作しただけではなく、その動作時間はまったく新しいレベルに達していました。

これほど大きな数を理解するには、馴染みのある加算と乗算という数学に立ち返る必要があります。まず、ある数をn回足し合わせることから始めましょう。これはn倍の定義に過ぎません。逆に、ある数をn回掛け合わせると、それは累乗と呼ばれます。では、ある数を繰り返し累乗するとどうなるでしょうか？この処理は、上向きの2つの矢印で示されるテトレーションと呼ばれる新しい演算を定義します。

テトレーションは急速に大きくなります。10↑↑1はただの10です。しかし、10↑↑2は10の10乗、つまり100億です^。そして10↑↑3は10の100億乗、つまり1の後に100億のゼロが続く数です。すべての数字を書き出すには、1000フィートの高さの紙の山が必要です。10↑↑4では、もはや十分な紙を見つける問題ではなくなる、象徴的な境界を超えます。宇宙に存在する原子の数よりもはるかに多くの数字が存在するのです。

リゴツキがクロピッツの記録を二度目に破ったのは、6つのルールを持つチューリングマシンで、10↑↑5ステップ以上実行して停止した時だった。クロピッツは10↑↑15ステップ実行するマシンで対抗した。これは15階建ての10の塔に相当する。彼らは慣れ親しんだ数字の世界を遥かに超えたのだ。

「あれは一つの時代の終わりだった」とクロピッツ氏はダイレクトメッセージで書いた。

それはまた、別の意味で一つの時代の終わりでもありました。それまで、ビジービーバーゲームは競争であり、研究者は主に単独で作業していました。その後、ビジービーバーチャレンジが結成され、新たな共同作業の時代が到来しました。

新しいタイプのクレイジー

Busy Beaver Challengeは、2022年にコンピュータサイエンスの大学院生Tristan Stérinによって設立され、BB(5)の真の価値を厳密に証明するという明確な目的を持っていました。2024年夏、グループはmxdysという仮名でのみ知られる謎の新人の重要な貢献により、成功を収めました。

結果のニュースはQuantaに掲載され、バージニア工科大学でコンピュータサイエンスの学部生を務めるケイトリン・ドゥセッテは偶然それを目にした。彼女はすぐにBusy Beaver Challengeコミュニティに参加し、最初はDiscordサーバーに時々立ち寄る程度だった。しかし5月に彼女は刺激的な発見をし、それ以来、BB(6)探索に最も積極的に参加する一人となった。「すっかり夢中になってしまいました」と彼女は言う。「本当に美しい問題集ですから」

BB(5)の証明に最後の仕上げを施してから1年、mxdysはBB(6)問題の解決に着実に取り組み、数千台を除くすべての「ホールドアウト」マシンを高度な自動化手法を用いて分類してきた。Doucetteはホールドアウトマシンのリストを調べていたところ、特に有望そうなマシンを見つけた。Shawn Ligockiの協力を得てさらに分析を進めたところ、そのマシンの実行時間はKropitzのチャンピオンマシンに次ぐ2番目であることを発見した。さらに、Doucetteのマシンはシフトオーバーフローカウンタと呼ばれる種類のマシンに属し、Kropitzのチャンピオンマシンとは全く異なるメカニズムを用いて長時間の実行時間を実現していた。

「この多忙なビーバーたちが新しい技術を発見したことは、とてもうれしい」とリゴッキ氏は語った。

これまでにも、他の数人の忙しいビーバーハンターが、長時間で停止するシフトオーバーフローカウンタを発見していたが、ドゥセッテの発見によって、研究チームは、こうした機械が自分たちが認識していたよりもたくさんあるのではないかと疑うようになった。そして、研究対象となった最初のもののいくつかがクロピッツの記録に迫っていたとすれば、他のものはそれを上回る可能性が高いだろう。ビジービーバーチャレンジの貢献者たちは、他のシフトオーバーフローカウンタの分析を急いだが、先にそこにたどり着いたのは mxdys だった。6 月 16 日、彼らは 10↑↑10 ⁷ステップで停止する新しいチャンピオンを発見したと発表した。つまり、その実行時間は 1000 万階建ての高さの 10 の塔に相当する。この数字を数字の列として書き表すことは論外である。しかし、それをパワーの塔として書くことさえ危険である。12 ポイントのフォントで、その 10 の列は約 25 マイルに伸びることになる。

休暇中にこのニュースを目にしたクロピッツ氏は、タイトル喪失を潔く受け入れ、Discordサーバーに「残念ながら、今回は3日間のトリックは披露できません」と書き込んだ。彼にとって慰めとなる賞品があったのは幸いだった。1ヶ月前、彼は7ルール・チューリングマシンの最長動作記録を樹立していたのだ。少なくとも今のところ、クロピッツ氏はまだリーダーボードに名を連ねている。

最大を超えて

この新記録は長くは続かなかった。1週間後、mxdysが再び記録を破った。そのマシンの実行時間は、またしても質的に新しいレベルに達した。この記録を最も簡潔に記述するには、「ペンテーション」と呼ばれる、上向きの3つの矢印で表される、突飛な数学演算を導入する必要がある。ペンテーションとは、テトレーションの繰り返しであり、言い換えれば、テトレーションと指数の関係は、ペンテーションとテトレーションの関係と同じである。

mxdysの新チャンピオンが停止するまでに踏んだ歩数の合計は2↑↑↑5、つまり2↑↑(2↑↑(2↑↑(2↑↑2))) よりも大きかった。この式を紐解くには、一番内側の括弧から外側に向かって計算していく。2↑↑2は4、2↑↑4は65,000を少し超える。つまり2↑↑(2↑↑65,000)となり、最終的に積み重なる2の高さは計り知れないほど大きくなる。何マイルも、あるいは何メガパーセクも続く巨大なパワータワーを書くことは諦めよう。このよりコンパクトな表記でさえ、もはや宇宙には収まらない。

この新たな結果はBB(6)の下限値に過ぎず、真の値はさらに高い可能性があります。多忙なビーバーハンターたちは、すぐに決定的な答えが得られるとは期待していません。最初の兆候は、昨年mxdysによって発見され、チームが「アンチヒドラ」と名付けた、巨大な6ルールのチューリングマシンでした。

アンティヒドラが停止することはほぼ確実だ。しかし、研究者たちはそれを証明できていない。それには十分な理由がある。ラシェリーヌという名の多忙なビーバーハンターが、アンティヒドラが停止するかどうかという問題は、数学における有名な未解決問題「コラッツ予想」と密接に関連していることを示したのだ。それ以来、研究チームは同様の特徴を持つ6ルールマシンを数多く発見してきた。アンティヒドラとその仲間を倒すには、純粋数学における概念的なブレークスルーが必要となるだろう。

しかし、忙しくて熱心なビーバーハンターにとって、落胆する必要はありません。6ルールのチューリングマシンはまだまだ数千種類存在し、それぞれが独自の豊かな動作をします。

「私にとって、数学をやる一番の理由は、楽しいから。芸術みたいなものよ」とレイチェリンはDiscordのダイレクトメッセージに書いた。「常に何か新しいことがあるはず」

オリジナルストーリーは、数学、物理科学、生命科学の研究の進展や動向を取り上げることで科学に対する一般の理解を深めることを使命とする、 シモンズ財団の編集上独立した出版物であるQuanta Magazineから許可を得て転載されました。