エデンの園配置
出典: フリー百科事典『ウィキペディア（Wikipedia）』
エデンの園配置（英: Garden of Eden pattern）とは、セル・オートマトンにおいて他のいかなる配置からも到達できない配置を指す。以前の状態が存在しない、つまり最初からそのように配置しない限り出現しないということから、聖書のエデンの園にちなんで命名された。
Moore (1962) によれば、1950年代に John Tukey が命名したもので、これはジョン・ホートン・コンウェイがライフゲームを発明するずっと前のことである。
目次 |
[編集] エデンの園の定理
ある時点 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]。
[編集] 小説におけるエデンの園配置
グレッグ・イーガンの小説『順列都市』において、セル・オートマトンの「エデンの園配置」の概念が重要な役割を果たす。
[編集] 外部リンク
[編集] 参考文献
- 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.
