エデンの園配置
エデンの園配置（エデンのそのはいち、英: Garden of Eden pattern）とは、セル・オートマトンにおいて他のいかなる配置からも到達できない配置を指す。以前の状態が存在しない、つまり最初からそのように配置しない限り出現しないということから、聖書のエデンの園にちなんで命名された。
Moore (1962) によれば、1950年代にジョン・テューキーが命名したもので、これはジョン・ホートン・コンウェイがライフゲームを発明するずっと前のことである。
エデンの園の定理
[編集]ある時点 t における配置を Ct とし、関数（オートマトン） f が配置 Ct から Ct+1 への写像であるとする。
エデンの園配置 Gt は、f(Gt-1)=Gt となる配置 Gt-1 が全く存在しないことを意味する。すなわち、エデンの園配置を持つセル・オートマトンは全射ではない。
セル・オートマトンの別の特性として「可逆性（reversivility）」がある。すなわち、ある配置 Ct についてその1つ前の配置 Ct-1 が一意に定まることをいう。この場合のセル・オートマトンは全単射である。全単射の定義から、エデンの園配置を持つセル・オートマトンは可逆ではないことが明らかである。実際、単射ではない全てのセル・オートマトンにはエデンの園配置がある。Edward F. Moore と John Myhill が証明したエデンの園の定理（Garden of Eden theorem）によれば、エデンの園配置を持たないときだけセル・オートマトンは可逆である。ライフゲームが可逆でないことは明らかであり、発見前からライフゲームにはエデンの園配置があることが分かっていた。
エデンの園の探索
[編集]Jean Hardouin-Duparc (1972, 1974) は計算によってエデンの園配置を探そうとした最初の人物であり、非決定性有限状態機械に受理される言語の差集合の構築という手法を使った。この有限状態機械は固定幅の配置を行単位に認識していくもので、1つ前のパターンがある配置を受理する。従って、その補集合がその幅の全てのエデンの園配置を表す正規言語となる。
2006年3月4日、Nicolay Beluchenko は既知のエデンの園配置に基づいて新しい最小のエデンの園配置を発見したと発表した[1]。 このエデンの園配置は12×12の大きさであり生きているセルは80である。
最小のエデンの園配置は定義によって変わるが、長辺が最小である10×10内に生きているセルが56存在する配置[2]（最小のオーファンを持つ配置でもある）、短辺が最小である5×83内に生きているセルが284存在する配置[3]、面積が最小である8×12内に生きているセルが57存在する配置[4]などが発見されている。
また、6×6内にエデンの園配置が存在しないことが示されている[5]。
オーファン
[編集]オーファンはエデンの園配置とよく似た概念である。 エデンの園配置は以前の状態が存在しない長方形を指すことが多いが、オーファンは配置の領域が有限であり形は長方形に限らない。 そのため、オーファンのセルの数はエデンの園配置のセルの数から「エデンの園配置内部に存在する生きていても死んでいても良いセルの数」を引いた数となる。
小説におけるエデンの園配置
[編集]グレッグ・イーガンの小説『順列都市』において、セル・オートマトンの「エデンの園配置」の概念が重要な役割を果たす。
参考文献
[編集]- Hardouin-Duparc, J. (1972/73). “À la recherche du paradis perdu”. Publ. Math. Univ. Bordeaux Année 4: 51–89.
- Hardouin-Duparc (1974). “Paradis terrestre dans l’automate cellulaire de Conway”. Rev. Française Automat. Informat. Recherche Operationnelle Ser. Rouge 8 (R-3): 64–71.
- Moore, E. F. (1962). “Machine models of self-reproduction”. Proc. Symp. Applied Mathematics 14: 17–33.
- Myhill, J. (1963). “The converse of Moore's Garden-of-Eden theorem”. Proceedings of the American Mathematical Society 14: 685–686.