エデンの園（セルオートマトン）
前例のないパターン

1971年にR・バンクスによって発見された、コンウェイのライフゲームにおけるエデンの園。 [1]画像の外側の細胞はすべて死んでいる（白）。
Achim Flammenkamp が発見した「Life」の孤児。黒い四角は必須の生細胞、青い×は必須の死細胞です。

セルオートマトンにおいて、エデンの園とは、先行する構成を持たない構成のことである。これはオートマトンの 初期構成となることはできるが、他の方法では発生しない。ジョン・チューキーは、これらの構成を、アブラハムの宗教におけるエデンの園にちなんで名付けた。エデンの園はどこからともなく創造された。[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]は、セルオートマトン遷移関数が構成空間上の並進不変連続関数とまったく同じであるというカーティス・ヘドランド・リンドン定理に基づく位相的議論を用います。[14]ここで、連続性は、オートマトンの状態の有限集合に離散位相を割り当て、次にオートマトンの各セルに対して積に1つの項を持つ積位相を使用して、オートマトンの構成を点とする位相空間を構築することによって定義されます。ティコノフの定理によれば、それはコンパクト空間です。[12]

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

エデンの園の定理

セルオートマトンにおいて、2つの有限パターンは、将来の構成を変えることなく、いずれか一方が他方と置換できる場合、双子と呼ばれます。セルオートマトンが単射的であるとは、オートマトンの各異なる構成のペアが、オートマトンの各ステップの後に異なるままであることを意味します。また、双子が存在しない場合には、局所単射的であるとも言えます。セルオートマトンが単射的であるのは、すべての構成に先行する構成が存在する場合、つまり、エデンの園のような構成を持たない場合のみです。単射的かつ単射的なオートマトンを可逆セルオートマトンと呼びます。[3]

エドワード・F・ムーア （1962年）とジョン・マイヒル（1963年）によるエデンの園定理は、ユークリッド空間における セルオートマトンが局所的に単射的である必要十分条件であり、かつそれが射影的である必要十分条件であると主張している。言い換えれば、セルオートマトンがエデンの園を持つ必要十分条件であり、かつそれが双子を持つ必要十分条件であると主張している。より強い主張として、局所的に単射でないセルオートマトンはすべて孤児パターンを持つ。直近の系として、単射的なセルオートマトンはすべて射影的でなければならない。ムーアは定理の一方向性、すなわち双子を持つオートマトンには孤児が存在することを証明した。[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の時空間図。非単射であるにもかかわらず、エデンの園は存在しない。各行は配置を表し、時間は下向きに進む。

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

静止状態の場合

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

非ユークリッド幾何学において

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

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

フィクションでは

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

注釈

  1. ^ ab ライフライン第3巻（1971年9月）で、編集者のロバート・T・ウェインライトは、ロジャー・バンクスとスティーブ・ワードが、生きた細胞が9×33の長方形に収まるエデンの園の存在を証明したと発表し、バンクスがエデンの園であると信じていた配置を提示しました。ライフライン第4巻（1971年12月）で、ウェインライトは、ハネウェルのグループがドン・ウッズのソフトウェアを使用して、バンクスの構成がエデンの園であることを検証したと報告しました。ガードナー（1983）も参照してください
  2. ^ ab ムーア (1962)。
  3. ^ abc Kari (2012)、セクション2.1「基本定義」、pp.5–6。
  4. ^ ab Toffoli & Margolus (1990)。ただし、ToffoliとMargolusは遷移関数をグローバルマップと呼んでいる点に注意。
  5. ^ カリ（2012）、10頁。
  6. ^ abc Kari (2012)、11ページ。
  7. ^ Kari (1990); Kari (1994). Kariの主な結果は、セルオートマトンが可逆的かどうかをテストすることは決定不可能であるということだが、彼はまた、エデンの園が存在するかどうかをテストすることも決定不可能であることを示している。
  8. ^ Toffoli & Margolus (1990)：「たとえ総当たり検索に頼る覚悟があったとしても、長い検索時間で生成されるアイテムはわずかで、そのほとんどもあまり興味深いものではないだろう。」
  9. ^ アルドゥアン=デュパルク (1972–73)。
  10. ^ アルドゥアン＝デュパルク（1974年）。
  11. ^ Flammenkamp (2016).
  12. ^ abcd Kari (2012)、命題2、p.11。
  13. ^ この結果の1次元の場合、Hedlund (1969) の定理5.1がそれである。ここで示したより単純な証明と同様に、配置空間のコンパクト性を利用している。ムーアとマイヒルは以前の研究において、孤児群とエデンの園を区別せず、孤児群のみを用いて結果を証明した。
  14. ^ Hedlund（1969）、定理3.4。
  15. ^ ab Myhill (1963).
  16. ^ ガードナー（1983年）。
  17. ^ サトナー（1991年）。
  18. ^ アモロソとクーパー (1970);スカイム（1975）。
  19. ^ Margenstern (2009). Margensternはこの成果を自身とJarkko Kariの共同の功績であると主張している。
  20. ^ チェッケリーニ＝ジルベスタイン、マッヒ、スカラボッティ (1999);カポビアンコ、ギヨン、カリ (2013);バルトルディ2019。
  21. ^ グロモフ（1999年）。
  22. ^ ゴットシャルク（1973年）。
  23. ^ Ceccherini-Silberstein & Coornaert (2010).
  24. ^ Blackford、Ikin、McMullen（1999年）; Hayles（2005年）。

参考文献

  • アモローソ、S.；クーパー、G.（1970）「有限配置に対するエデンの園の定理」、アメリカ数学会誌、26（1）：158–164、doi：10.1090/S0002-9939-1970-0276007-5
  • バルトルディ、ローラン（2019）「群の従順性はマイヒルの定理によって特徴付けられる」、ヨーロッパ数学会誌、21（10）、ダヴィド・キエラックによる付録付き：3191–3197、arXiv：1605.09133、doi：10.4171/JEMS/900、MR  3994103
  • ブラックフォード、ラッセル、アイキン、ヴァン、マクマレン、ショーン（1999年）「グレッグ・イーガン」『奇妙な星座：オーストラリアSFの歴史』、SFとファンタジーの研究への貢献、第80巻、グリーンウッド出版グループ、190～200頁、ISBN 978-0-313-25112-2
  • カポビアンコ、シルヴィオ；ギヨン、ピエール；カリ、ヤルッコ(2013)、「エデンの園から遠く離れた射影セルオートマトン」、離散数学と理論計算機科学、15 (3): 41–60、MR  3141826
  • Ceccherini-Silberstein, Tullio; Coornaert, Michel (2010)、「Surjunctive groups」、Cellular automata and groups、Springer Monographs in Mathematics、Springer-Verlag、pp.  57– 75、doi :10.1007/978-3-642-14034-1_3、ISBN 978-3-642-14033-4、MR  2683112
  • Ceccherini-Silberstein, TG; Machì, A.; Scarabotti, F. (1999)、「Amenable groups and cellular automata」、Annales de l'Institut Fourier、49 (2): 673– 685、doi : 10.5802/aif.1686、MR  1697376
  • フラメンカンプ、アヒム（2016年4月）、「エデンの園／孤児」、アヒムの人生ゲームページ
  • ガードナー、マーティン（1983）、「第20章と第21章：ライフゲーム、パートIとII」（PDF）、Wheels, Life, and Other Mathematical Amusements、WH Freeman、pp.  214– 258特に230ページと248ページを参照
  • ゴットシャルク、ウォルター (1973)、「いくつかの一般的な力学概念」、位相力学の最近の進歩 (位相力学に関する会議録、イェール大学、ニューヘイブン、コネチカット州、1972年; グスタフ・アーノルド・ヘドランドを記念して)、数学講義ノート、第318巻、シュプリンガー・フェアラーク、pp.  120– 125、doi :10.1007/BFb0061728、ISBN 978-3-540-06187-8、MR  0407821
  • グロモフ、M. (1999)、「記号代数多様体の自己準同型」、ヨーロッパ数学会誌、1 (2): 109– 197、doi : 10.1007/PL00011162、MR  1694588、Zbl  0998.14001
  • Hardouin-Duparc, J. (1972–73)、「À la recherche du paradis perdu」、Publ.数学。大学ボルドー アネ、4 : 51– 89
  • Hardouin-Duparc, J. (1974)、「Paradis terrestre dans l'automate cellulaire de Conway」、Rev. Française Automat。情報を提供します。 Recherche Operationnelle Ser.ルージュ、8 (R-3)：64～ 71
  • ハートマン、クリスチャン。Heule, マリジン JH ;クウェッケブーム、キーズ。 Noels、Alain (2013)、「Symmetry in Gardens of Eden」、Electronic Journal of Combinatorics、20 (3): P16、doi : 10.37236/2611、MR  3104514
  • ヘイルズ、N.キャサリン（2005）「主観的宇宙論と計算体制：グレッグ・イーガンのフィクションにおける媒介」『私の母はコンピュータだった：デジタル主体と文学テクスト』シカゴ大学出版局、pp.  214– 240、ISBN 978-0-226-32147-9
  • ヘドランド、GA (1969)、「シフト力学系の準同型と自己同型」、数理システム理論、3 (4): 320– 375、doi :10.1007/BF01691062、S2CID  21803927
  • カリ、ヤルッコ（1990）、「2次元セルラーオートマトンにおける可逆性は決定不能である」、Physica D、45（1-3）：379-385、Bibcode：1990PhyD...45..379K、doi：10.1016/0167-2789(90)90195-U
  • カリ、ヤルッコ（1994）、「セルラーオートマトンにおける可逆性と射影性の問題」、コンピュータとシステム科学ジャーナル、48（1）：149–182、doi：10.1016/S0022-0000（05）80025-X、MR  1259654
  • Kari, Jarkko J. (2012)、「セルラーオートマトンの基本概念」、Rozenberg, Grzegorz; Bäck, Thomas; Kok, Joost N. (編)、『自然コンピューティングハンドブック』、Springer、pp.  3– 24、doi :10.1007/978-3-540-92910-9_1、ISBN 978-3-540-92909-3
  • マーゲンシュテルン、モーリス (2009)、「双曲面におけるセルオートマトンにおけるエデンの園の定理について」、第15回セルオートマトンと離散複雑系国際ワークショップ、理論計算機科学の電子ノート、第252巻、pp.93-102  、 doi : 10.1016 /j.entcs.2009.09.016
  • ムーア, EF (1962)、「自己複製の機械モデル」、生物科学における数学的問題、応用数学シンポジウム論文集、第14巻、pp.  17– 33、doi :10.1090/psapm/014/9961、ISBN 9780821813140{{citation}}: CS1 メンテナンス: ISBN エラーを無視 (リンク);アーサー・W・バークス（1970年）『セルオートマトンに関するエッセイ』イリノイ大学出版局、  187～ 203ページに再録。
  • マイヒル、J. (1963)、「ムーアのエデンの園定理の逆」、アメリカ数学会誌、14 (4): 685–686、doi : 10.1090/S0002-9939-1963-0155764-9、JSTOR  2034301; Burks, Arthur W. (1970)『セルラーオートマトンに関するエッセイ』、イリノイ大学出版局、pp.  204– 205に再録。
  • スカイム、スヴェン（1975）「エデンの園における混乱」アメリカ数学会誌、50（1）：332-336、doi：10.1090/S0002-9939-1975-0386350-1
  • Sutner、Klaus (1991)、「De Bruijn グラフと線形セル オートマトン」(PDF)、Complex Systems、5 : 19–30、MR  1116419
  • トッフォリ, トマソ;マーゴラス, ノーマン(1990)、「可逆セルラーオートマトン：レビュー」、Physica D: 非線形現象、45 ( 1– 3): 229– 253、Bibcode :1990PhyD...45..229T、doi :10.1016/0167-2789(90)90185-R、MR  1094877
「https://en.wikipedia.org/w/index.php?title=Garden_of_Eden_(cellular_automaton)&oldid=1306332669#The_Garden_of_Eden_theorem」より取得