エデンの園の定理
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2016/08/28 03:34 UTC 版)
ある時点 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）によれば、エデンの園配置を持たないときだけセル・オートマトンは可逆である。ライフゲームが可逆でないことは明らかであり、発見前からライフゲームにはエデンの園配置があることが分かっていた。
※この「エデンの園の定理」の解説は、「エデンの園配置」の解説の一部です。
「エデンの園の定理」を含む「エデンの園配置」の記事については、「エデンの園配置」の概要を参照ください。
ウィキペディア小見出し辞書の「エデンの園の定理」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- エデンの園の定理のページへのリンク
