5番目のビジービーバーで研究者たちが計算の限界に迫る
(quantamagazine.org)-
導入部
- 40年前、ドイツのドルトムントでコンピューター科学者たちが集まり、5番目のビジービーバーを見つけるために競い合った
- ビジービーバーは単純なコンピュータープログラムだが、実行時間が非常に長くなる
- これらのプログラムは数学の有名な未解決問題と関係しており、コンピューター科学の古い問題に由来する
- 2年前、大学院生のTristan Stérinがビジービーバー・チャレンジを始め、世界中から20人以上の貢献者が参加した
- 今日、チームはBB(5)の値が47,176,870であることを確認した
-
停止するのか、しないのか
- ビジービーバー・プログラムは、チューリングマシンという理論上のコンピューター向けの命令で書かれる
- チューリングマシンは無限テープ上で0と1を読み書きしながら計算を行う
- チューリングマシンが停止するのか永遠に実行されるのかを予測する問題を停止問題という
- 停止問題には一般的な解法がなく、それがビジービーバー探索をいっそう魅力的なものにしている
-
ビーバーの登場
- 数学者Tibor Radóは1962年にビジービーバー・ゲームを考案した
- 各ルール群の中で最も長く実行されるチューリングマシンをビジービーバーと呼ぶ
- BB(n)は、n個のルールを持つビジービーバー・マシンが停止するまでにかかるステップ数を表す
-
ブレイディのビーバー群
- Allen Bradyは1960年代にビジービーバー探索の技法を開発し、1974年に4番目のビジービーバーの値を決定した
- BB(4)は107ステップ後に停止するマシンであることが確認された
-
5番目のビーバー
- 1984年のドルトムント大会で、5番目のビジービーバーを見つけるための最初の大規模な探索が始まった
- 1989年、Heiner Marxenは47,176,870ステップ後に停止するマシンを発見した
- 2003年、Georgi Georgievは43台の未解決チューリングマシンを残したまま、BB(5)探索を中断した
-
すべてのハンターを招集
- Tristan Stérinは2022年にビジービーバー・チャレンジを開始し、世界中の貢献者たちが参加した
- Shawn Ligockiは2022年にチームに加わり、重要な貢献を果たした
- Justin Blanchardは、チームの最も強力な技法の1つであるclosed tape language法を開発した
-
怪物への接近
- Skelet #1と#17は特に難しいマシンで、チームはこれを解くためにさまざまなアイデアを組み合わせた
- 2023年5月、mxdysという匿名の貢献者がCoqによる証明を完了した
-
ビーバーが歩き回る場所
- チームは正式な学術論文を執筆中であり、一部のメンバーは次のビーバーを見つけるために取り組んでいる
- BB(6)はCollatz予想に似た問題のため、解決が難しいと見られている
GN⁺の見解
- この記事は、コンピューター科学の限界を探る興味深い事例を示している
- ビジービーバー・チャレンジは、協調的な研究の重要性を示している
- BB(5)の解決は、コンピューター科学および数学コミュニティにとって大きな意味を持つ
- 類似の性質を持つプロジェクトとして、Collatz予想の研究がある
- 新しい技術やオープンソースを採用する際には、協力と再現可能性が重要である
1件のコメント
Hacker Newsの意見
Scott Aaronsonのブログ記事に関する意見が共有されている
Busy Beaver問題にはさまざまな変種が存在する
あるエンジニアがBusy Beaver問題を研究するために仕事を辞めた話が共有されている
Coqによる証明への言及がある
Tibor Radóの元のBusy Beaver論文は読みやすくて面白いという意見がある
5状態2色のTuring機械プログラムの停止問題が解決された
人間が停止問題を直感的に解決できるという誤った考えへの言及がある
個人プロジェクトでCutting Stock問題を解くためのプログラムを書いた経験が共有されている
5状態のTuring機械プログラムの停止を証明できたのは運が良かったという意見がある
Scott Aaronsonのブログ記事によると、16,679,880,978,201個の5状態Turing機械が存在する
Busy Beaver関数の値が共有されている