1969 年、英国の数学者ジョン コンウェイは、複雑な動作を作成するための魅惑的に単純な一連のルールを考案しました。彼のライフ ゲームは、単にライフと呼ばれることが多く、無限の正方形のセルで展開されます。各細胞は「生きている」ことも「死んでいる」こともあります。グリッドは一連のターン (または「世代」) を経て進化し、各セルの運命はそれを囲む XNUMX つのセルによって決定されます。ルールは次のとおりです。

1. 誕生: ちょうど 3 つの生きた隣接セルを持つ死んだセルが生きます。
2. 生存: 2 つまたは 3 つの生きた隣接セルを持つ生きたセルは生き続けます。
3. 死: 生きている隣接セルが 2 つ未満または 3 つ以上ある生きているセルは死にます。

これらの単純なルールは、驚くほど多様なパターン、つまり「生命体」を作成し、グリッドのさまざまな開始構成から進化します。ゲームの愛好家たちは、これらのパターンを集計し、分類し、拡大し続けています。 オンラインカタログ。コンウェイは、2 つの状態の間を行き来するブリンカーと呼ばれるパターンを発見しました。

翌年、彼はパルサーと呼ばれる、3 つの異なる状態の間で振動するさらに複雑なパターンを発見しました。

オシレーターが発見されてすぐ、ゲームの初期の探索者たちは、あらゆる時代のオシレーターが存在するかどうか疑問に思いました。 「最初は周期 1、2、3、4、15 しか見えませんでした」とコンピュータープログラマーで数学者のビル・ゴスパーは述べました。彼はその後数十年にわたって 17 種類の新しい発振器を発見することになります。期間 15 のオシレーター (以下を参照) は、ランダム検索で驚くほど頻繁に見つかりました。

見つけようとする人には驚きが潜んでいます。 「何時間も何日も見ていたから、第5期は不可能に思えた」とゴスパー氏は語った。そして、ゲームが発明されてから 1971 年後の XNUMX 年に、ゲームが発見されました。新しいオシレーターの探索はゲームの主要な焦点となり、コンピューター技術の出現によってその探求が強化されました。オフィスのコンピューター上で行われた秘密捜査の記録は、ゲームの民間伝承の基礎となっています。 「企業や大学のメインフレームから盗まれたコンピュータ時間の量は驚くべきものでした」とゴスパー氏は語った。

1970 年代を通じて、数学者や愛好家は他の短い期間を埋めて、わずかに長い期間を見つけました。最終的に、数学者は長周期発振器を構築する体系的な方法を発見しました。しかし、周期が 15 ～ 43 のオシレーターを見つけるのは困難であることが判明しました。 「人々は何年もの間、その中間を見つけようとしてきました」と彼は言いました。 マイア・カルポビッチ、メリーランド大学の大学院生。ギャップを埋めるために、研究者たちは、数学者が進化するグリッドを生命のようなものと呼ぶように、セルオートマトンで可能だと考えられていたことの限界を押し上げる、数多くの新しい技術を考案することを余儀なくされました。

今回、カルポビッチと6人の共著者は、ある論文で発表した。 XNUMX月のプレプリント 彼らは、欠落していた最後の 19 つの期間、41 と XNUMX を見つけたということです。これらのギャップが埋められたことで、生命は「全周期的」であることが現在知られています。正の整数に名前を付けてください。これだけ多くのステップを経た後に繰り返されるパターンが存在します。

ライフの研究に専念する急成長中のコミュニティには、多くの数学研究者だけでなく愛好家も含まれており、発振器だけでなくあらゆる種類の新しいパターンも発見されています。彼らは、グリッドを横切って移動するパターン、宇宙船と呼ばれるパターン、および銃、コンストラクター、ブリーダーなどの他のパタ​​ーンを構築するパターンを発見しました。彼らは、素数を計算するパターン、さらには任意の複雑なアルゴリズムを実行できるパターンを発見しました。

周期が 15 より短いオシレーターは、手動で見つけることも、一度に 31 セルずつオシレーターを検索する初歩的なアルゴリズムを使用して見つけることもできます。しかし、期間が大きくなるにつれて複雑さも増し、総当たり検索の効果は大幅に低下します。 2010年に最初の周期2021発振器を発見したこの新しい論文の共著者であるマティアス・メルゼニヒ氏は、「短い周期であれば、直接検索することができる。しかし、実際にはそれを超えることはできない。期間を選択して検索することはできません。」 (メルゼニッチ氏は XNUMX 年にオレゴン州立大学で数学の博士号を取得しましたが、現在は農場で働いています。)

1996 年、カナダのフリーランス コンピュータ コンサルタントであり、1970 年代後半からパターンを探索していたライフ愛好家であるデビッド バッキンガムは、無限ループで閉じたトラックの周囲にパターンを送信することで、周期 61 以上の発振器を構築できることを示しました。 。バッキンガムは、ループの長さと、パターンが 61 往復するのにかかる時間を制御することで、周期を好きなだけ長くできることを発見しました。 「変な匂いや割れたガラス製品のない化学です」と彼は言う。 「化合物を構築して、それらの間の相互作用を探索するようなものです。」これは、彼が XNUMX 周期より長ければ、任意の長周期の発振器を構築する方法を一気に思いついたことを意味します。

1990 年代半ばには、15 から 61 までの失われたオシレーターの多くが、カラフルな名前が付けられていた既知のオシレーターを創造的に組み合わせることによって発見され、数多くの結果が得られました。ケータリングは信号機と組み合わされ、火山は火花を吐き、食べる人はグライダーを食べました。

21 世紀初頭までに、まだ残っている期間は 2013 個だけでした。 「この問題を解決することは非常に可能だと思われました」とメルゼニヒ氏は語った。 1996 年、スナーク ループと呼ばれる新しい発見により、バッキンガムの 61 年の技術が改良され、発振器の構築が容易になるカットオフが 43 から 2019 に引き下げられました。これにより、欠落した周期は 2022 つだけになりました。 19年にさらに41つ、XNUMX年にさらにXNUMXつが発見され、残ったのはXNUMXとXNUMXだけで、どちらも素数だった。 「素数は、短周期発振器を使用して構築できないため、より困難です」とメルゼニヒ氏は言います。

ニューヨーク大学アブダビ校の博士研究員であり、この新しい論文のもう一人の共著者であるミッチェル・ライリー氏は、ハスターと呼ばれる一種の発振器に長い間興味を持っていた。 「迷惑行為の仕組みは、真ん中にアクティブなパターンがあり、外側にそれに反応する安定したものがあるということです」とライリー氏は説明しました。触媒と呼ばれる安定した物質は、活性パターンを元の状態に戻すために存在します。

それらをデザインするのは難しいです。 「これらのパターンはどれも信じられないほど壊れやすいものです」とライリー氏は言う。 「1 つの点を所定の位置からずらして配置すると、通常は爆発してしまいます。」

ライリーは、新しい触媒を探すために Barrister と呼ばれるプログラムを作成しました。 「私たちが求めているのは、丈夫な静物画です。重要なのは、彼らが途中で起こっていることと対話してから回復してほしいということです」とライリー氏は語った。

ライリーは、バリスターが見つけた触媒を別の検索プログラムに供給し、それらをアクティブなパターンと組み合わせました。これが主に失敗につながった、と彼は言う。 「これらの触媒のうちの 1 つが相互作用を経て生き残ることはかなりまれです。成功する保証はありません。あなたはただ指を交差させて、ジャックポットが当たることを願っているだけです。ちょっとギャンブルっぽい感じがしますね。」

結局、彼の賭けは報われました。数回のニアミスと、対称パターンを含むように検索を拡張するコードの修正の後、彼は周期 19 の発振器を維持できる触媒相互作用を発見しました。 「人々は、たくさんの触媒とその中間にある珍しい活性物質を使って、あらゆる種類の非常に複雑な探索を試みてきましたが、必要なのは、この新しい分厚い触媒を見つけることだけでした」とライリー氏は語った。

欠落していた最後のピリオド 41 は、別の共著者で現在もカリフォルニア大学サンタクルーズ校で数学を専攻しているニコロ・ブラウンによって発見されました。ブラウンはグライダーを触媒として使用しましたが、これはメルゼニヒが最初に提案したアイデアです。

「私たちは過去10年間で非常に多くの深い行動を発見しました」とカルポビッチ氏は語った。 「誰もが XNUMX 週間お祝いをしますが、その後は別のことに移ります。他にも解決すべき問題が山ほどあります。」特定の周期の発振器を小さくすることはできますか?すべての細胞が振動する発振器を見つけることができるでしょうか?銃は特定の時代に作られるのでしょうか？宇宙船を特定の速度で航行させることはできるのでしょうか?

バッキンガムが言うように、「無限のおもちゃ屋にいる子供のようなものです」。