エデンの園（セルオートマトン）

セルオートマトンにおいて、エデンの園とは前例のない構成である。これはオートマトンの初期構成となることはできるが、他の方法では発生しない。 ジョン・テューキーは、どこからともなく創造されたアブラハムの宗教のエデンの園にちなんで、これらの構成に名前を付けた。 ^[2]

エデンの園は、オートマトン（通常は 1 次元または 2 次元の無限正方格子のセル）内のすべてのセルの状態によって決まります。ただし、どのエデンの園にも有限のパターン（セルとその状態のサブセットで、孤児と呼ばれます）が存在します。このパターンは、残りのセルがどのように埋められても、先行するセルがないという同じ特性を持ちます。オートマトン全体の構成がエデンの園になるのは、孤児が含まれている場合のみです。1 次元セルオートマトンの場合、孤児とエデンの園は効率的なアルゴリズムによって見つけることができますが、高次元の場合、これは決定不可能な問題です。それでも、コンピューター検索により、コンウェイのライフゲームでこれらのパターンを見つけることに成功しています。

ムーアとマイヒルのエデンの園の定理は、正方格子上、または任意の高次元ユークリッド空間のタイリング上のセルオートマトンがエデンの園を持つためには、双子、つまり一方が他方に置き換えられても同じ後継パターンを持つ 2 つの有限パターンが必要であることを主張しています。

セルオートマトンとは、セルのグリッド、各セルに割り当てることができる有限の状態セット、および更新ルールによって定義される。多くの場合、セルのグリッドは 1 次元または 2 次元の無限正方格子である。更新ルールは、各セルの現在の状態と、特定の他の近くのセル (セルの近傍)の現在の状態の関数として、各セルの次の状態を決定する。近傍は任意の有限のセルセットにすることができるが、各 2 つのセルは同じ相対位置に隣接するセルを持つ必要があり、すべてのセルは同じ更新ルールを使用する必要があります。オートマトンの構成は、すべてのセルに状態を割り当てることです。^[3]

ある構成の後継とは、更新規則をすべてのセルに同時に適用することで形成される別の構成です。[ 4 ^{]オートマトンの}状態遷移関数 は、各構成をその後継にマッピングする関数です。^[3]構成X の後継が構成Yである場合、X はYの前継です。構成には 0 個、1 個、またはそれ以上の前継が存在する可能性がありますが、後継は常に 1 個だけ存在します。^[4] エデンの園は、前継が 0 個の構成として定義されます。^[5]

パターンは、与えられたセルオートマトンに対して、有限のセル集合と、各セルの状態から構成される。^[6]パターン内のセルの状態が構成内の同じセルの状態と同じである場合（一致させる前にセルを変換しない場合）、構成にはパターンが含まれる。構成の先行定義は、パターンの先行にまで拡張できる。パターンの先行とは、後続にパターンが含まれる構成のことである。したがって、孤立パターンとは、先行がないパターンである。^[6]

1次元セルオートマトンの場合、エデンの園は、実行時間がオートマトンルールテーブルのサイズの多項式である効率的なアルゴリズムによって見つけることができます。より高次元の場合、エデンの園が存在するかどうかを判断することは決定不可能な問題であり、終了して正しい答えを生成することが保証されるアルゴリズムは存在しません。^[7]ただし、多くの場合、エデンの園の定理（以下）を使用して解が存在することを推測し、検索アルゴリズムを使用して解を見つけることができます。

コンピュータプログラムが、有限パターンをサイズの大きい順に体系的に調べ、各パターンのすべての可能な先行パターンをテストして、実際に孤児であるかどうかを判断することで、孤児パターンを検索することが可能です。しかし、この方法でエデンの園を見つけるために生成する必要があるパターンの数は、パターンの領域で指数関数的になります。この膨大な数のパターンにより、比較的小さなサイズのパターンであっても、この種のブルートフォース検索は非常に高価になります。 ^[8]

ジャン・アルドゥアン＝デュパルク（1972～73、1974）は、孤立パターンを見つけるためのより効率的な計算手法の先駆者となった。彼の方法は形式言語理論に基づいており、パターンの面積ではなく幅に比例する時間がかかる。重要なアイデアは、任意の固定幅について、 先行パターンが存在する特定の幅のパターンを認識する非決定性有限オートマトンを構築できるというものである。このマシンへの入力シンボルはパターンの各行を表し、マシンの状態は、これまでに入力されたパターンの部分に対する可能な先行パターンの近くの行を表す。このマシンから、べき集合構成を使用して非決定性有限状態マシンを決定性有限オートマトンに変換し、次にその受け入れ状態のセットを補完することにより、補完セット、つまり先行パターンを持たないパターンを認識する別の有限状態マシンを構築できる。補完集合を認識するマシンが構築されると、開始状態から受け入れ状態へのパスを検索することで、認識する言語が空であるかどうかをテストできます。このパスが存在する場合、孤立パターンの行ごとの説明が得られます。^[9]

マーティン・ガードナーは、エデンの園の定理がコンウェイのライフゲームに当てはまるという観察をアルビー・レイ・スミスに帰し、このルールでエデンの園の存在を証明した。ライフゲームで最初に明示されたエデンの園は、生きた細胞が9×33の長方形に収まるもので、1971年にロジャー・バンクスによってエデンの園の候補として特定され、その後、先行例を徹底的に遡って検索することで検証された。^{[1]その後、アルドゥアン＝デュパルクは形式言語アプローチを使用して、コンウェイのライフゲームで生きた細胞の}境界ボックスがわずか6セル幅である、 可能な限り狭いエデンの園を見つけた。 ^[10]

コンウェイのライフゲームにおける最小の孤立パターン（境界ボックスの面積で）は、2016年4月にスティーブン・エーカーによって発見されました。このパターンには57個の生きた細胞があり、8×12の長方形に収まります。^[11]

定義により、すべての孤児はエデンの園に属します。つまり、残りの各セルの状態を任意に選択することで、孤児をオートマトン全体の構成に拡張すると、常にエデンの園が生成されます。しかし、その逆もまた真です。すべてのエデンの園には、少なくとも 1 つの孤児が含まれます。^{[12] [13]} これを証明するために、Kari ^{[12] は}、セルオートマトンの状態遷移関数が構成空間上の変換不変連続関数とまったく同じであるというCurtis–Hedlund–Lyndon 定理に基づく位相的議論を使用します。^{[14]ここで、連続性は、オートマトンの状態の有限集合に}離散位相を割り当て、次に、オートマトンの各セルの積に 1 つの項を含む積位相を使用して、点がオートマトンの構成である位相空間を構築することによって定義されます。Tychonoffの定理により、これはコンパクトな空間です。^[12]

各有限パターンについて、そのパターンを含む構成の集合はこの位相における開集合であり、シリンダーと呼ばれる。^[6]シリンダーは位相の基底を形成する。カリが指摘するように、エデンの園ではない構成の集合は遷移関数の像にすぎないため、コンパクト空間の閉写像補題により閉集合となる。エデンの園の集合は、これに対応して開集合である。開集合でありシリンダーが基底を形成するため、エデンの園の集合はシリンダーの和集合として表すことができる。この和集合の各シリンダーはエデンの園のみで構成されるため、各シリンダーを決定するパターンは孤児でなければならない。エデンの園の集合が空でない場合、この和集合には少なくとも 1 つのシリンダーが存在するため、少なくとも 1 つの孤児が存在する。また、特定のエデンの園はこれらのシリンダーのいずれかに属している必要があり、したがってそのシリンダーの孤児を含んでいなければならない。^[12]

セルオートマトンでは、2 つの有限パターンは、将来の構成を変更することなく、どこに現れても一方を他方と置き換えることができる場合、双子である。セルオートマトンが単射であるのは、オートマトンの各異なる構成のペアがオートマトンの各ステップの後に異なるままである場合であり、双子がない場合には局所的に単射である。セルオートマトンが全射であるのは、すべての構成に先行するものがある場合、つまり、エデンの園の構成がない場合に限る。単射かつ全射であるオートマトンを可逆セルオートマトンと呼ぶ。^[3]

エドワード・F・ムーア (1962) とジョン・マイヒル (1963)によるエデンの園の定理は、ユークリッド空間内のセルオートマトンが局所的に単射的であるのは、それが射影的である場合に限ると主張している。言い換えれば、セルオートマトンがエデンの園を持つのは、それが双子を持つ場合に限ると主張している。より強い主張は、すべての非局所的に単射なセルオートマトンには孤児パターンがあるということである。直接の帰結として、単射なセルオートマトンが射影的である必要がある。ムーアは定理の1つの方向性、つまり双子を持つオートマトンには孤児がいることを証明した。^[2]マイヒルは逆のことを証明し、孤児を持つオートマトンにも双子がいることを証明した。^[15]

コンウェイのライフゲームの場合、双子は孤児よりも見つけやすい。例えば、死んだセルの5×5ブロックと、中央のセルだけが生きていて残りのセルが死んだ5×5ブロックは双子である。中央のセルの状態は、パターンの後の配置には影響しない。したがって、この場合、エデンの園定理により、エデンの園の存在は、明示的な孤児パターンを見つけるよりもはるかに簡単に証明できる。^[16]

定理の証明の主なアイデアは、計数議論を使用して、局所的な単射性の失敗 (双子パターン) は孤立パターンにつながり、その逆も成り立つことを示すことです。より詳細には、具体的には、オートマトンの基礎となる格子が 2 次元の正方格子であり、s 個の異なるセル状態があり、双子パターンPとQ は両方ともn × nの正方形に収まり、任意のセルの近傍の半径は最大でnであると仮定します。次に、 mn × mnの正方形に収まるパターンが孤立パターンかどうかを判断するには、 ( m + 2) n × ( m + 2) nの正方形に収まり、パターンQを含まない潜在的な先行パターンの部分を調べるだけで済みます。しかし、 これらの潜在的な先行パターンは( s ^{n × n} − 1) ^{( m + 2) × ( m + 2)個しかありません。} mの値が十分に大きい場合、この数は潜在的な孤児の数s ^{mn × mn}よりも小さくなります。したがって、潜在的な孤児の 1 つには先行パターンがなく、実際に孤児です。つまり、非単射性は非全射性を意味します。逆に ( n を孤児の境界ボックスのサイズとすると)、非常によく似た計数議論から、 ( m + 2) n × ( m + 2) nの正方形に収まり、孤児を含まないパターンの数は、mn × mnの正方形内のすべての開始パターンに明確な後続パターンを提供するには少なすぎることがわかります。このことから、可能性のある開始パターンのうちの 2 つは双子であることがわかります。したがって、非全射性は局所的な非単射性を意味します。^[15]

定理における単射性と局所単射性の区別は必要である。局所単射だが単射ではないセルオートマトンが存在するからである。一例として、ルール90がある。これは1次元バイナリオートマトンであり、その更新ルールは各セルの状態をその2つの隣接セルの排他的論理和に置き換える。このオートマトンでは、すべての状態が4つの先行状態を持つため、単射ではないがエデンの園も存在しない。^[17]

コンウェイのライフゲームのようなオートマトンには、特別な「静止」状態があり、静止セルの近傍が完全に静止している場合には静止状態のままである。この場合、「有限構成」を有限数の非静止セルのみを含む構成と定義することができる。静止状態を持つ非局所的単射セルオートマトンには、それ自体が有限構成であるエデンの園があり、たとえば孤児を含む有限構成がある。オートマトンが有限構成を持つことも可能であり、その前身は有限ではない（たとえば、ルール90では、単一のライブセルを含む構成がこの特性を持つ）。しかし、エデンの園定理は、そのようなパターンの存在を特徴付けるものではない。^[18]

双曲平面または高次元双曲空間のタイル張りで定義されたセルオートマトンでは、エデンの園定理の証明における計数議論は機能しない。なぜなら、この議論は、領域の境界が半径の関数としてその体積よりも遅く成長するというユークリッド空間の特性に暗黙的に依存するからである。双子を持つがエデンの園を持たない双曲セルオートマトンや、エデンの園を持つが双子を持たない双曲セルオートマトンが存在する。これらのオートマトンを、例えば、各頂点で3つの七角形が交わる一様双曲タイル張り、または各頂点で4つの五角形が交わる一様双曲タイル張りで回転不変な方法で定義することができる。^[19]

しかし、エデンの園の定理はユークリッド空間を超えて、従属群の元で定義されたセルオートマトンに一般化することができます。^[20]エデンの園の定理のより弱い形式は、すべての単射セルオートマトンが射影的であると主張しています。これは、代数幾何学における単射性と全単射性の間の類似関係であるアックス-グロタンディークの定理を使用して、ソフィック群に対して証明できます。 ^[21]より一般的には、この弱い形式が成り立つ群は、接尾群と呼ばれます。^[22]接尾的でない群の例は知られていません。^[23]

グレッグ・イーガンの小説『順列都市』では、主人公がエデンの園の構成を利用して、自分のコピーがシミュレーション内に住んでいることを証明できる状況を作り出す。これまで、彼のシミュレートされたコピーはすべて「現実世界」の何らかのバリエーションにいた。シミュレーション内に住むシミュレートされたコピーであるという記憶はあったが、その記憶がどのようにして生まれたのかについては、より単純な説明が常にあった。しかし、エデンの園の構成は、知的に設計されたシミュレーション以外では発生しない。宗教的な類似点は意図的なものである。^[24]

• LifeWiki のエデンの園
• エデンの園 (エリック・ワイススタインの人生ゲームの宝庫) 2009-01-06 にアーカイブされました ( Wayback Machineより)