セル・オートマトン
1940年代にロスアラモス国立研究所で働いていたスタニスワフ・ウラムは結晶の成長について研究していたとき、モデルとして単純な格子ネットワークを使用していた。同じころロスアラモスで一緒に働いていたジョン・フォン・ノイマンは自己複製機械を研究していた。フォン・ノイマンはまず、あるロボットの記述に基づいて別のロボットの記述を行うという設計を考えていた。この設計は運動学モデル(Kinematic model)と呼ばれている。設計を進めるに連れ、フォン・ノイマンは、複製を作るための「部品の海」をロボットに与えることのコストの膨大さやあるロボットが別のロボットを作るということを記述する大変さを徐々に理解していった。ノイマンは1948年の Hixon Symposium にて "The general and logical theory of automata" と題した論文を読む。またウラムはフォン・ノイマンに自己複製の還元主義的モデルとして離散系を使ってはどうかと示唆した。Nils Aall Barricelli はそういったモデルを使って人工生命を研究していた。
1950年代、ウラムとノイマンは液体の動きを計算する方法を生み出した。その中心となった考え方は液体を離散的単位の集まりとみなすということで、各単位の動作をその近傍の挙動に基づいて計算する。それらが元となってセル・オートマトンが生まれた。
Andrew Ilachinski は著書 Cellular Automata で、多くの学者が宇宙自体がセル・オートマトンなのではないかという疑問を投げかけていると指摘した。Ilachinskiは、この問題の重要性を示すには簡単な観察をしてみるのがよいと主張し、例えばルール110(英語版)の発展するパターンをどうやったらうまく説明できるか考えてみるのがよいとした。そして、もしそのイメージの生成方法を知らないとしたら、何らかの粒子状のオブジェクトの運動の軌跡ではないかと推測するだろうと述べている。実際、物理学者 James Crutchfield はその考え方から厳密な数学的理論を構築した。この考え方を推し進めていくと、素粒子物理学で説明されている我々の世界も根底ではCAと見なせるのではないかという考え方に到達する。
その考え方に沿った理論はまだ発展途中だが、この仮説に興味を惹かれた学者らが離散的フレームワークで世界を理解することについて興味深い憶測と有益な直観を示している。AI研究者マービン・ミンスキーは、4次元CA格子で素粒子の相互作用を理解する方法を研究した。
現在状態から1つ前の状態(プレイメージ)が一意に求められるセル・オートマトンを「可逆的」(reversible) であるという。セル・オートマトンを状態から状態への関数と考えると、可逆性はその関数が全単射であることを意味する。可逆型のセル・オートマトンは、時間を遡った際の挙動もセル・オートマトンとして記述できる。これは、セル・オートマトンを位相幾何学的に説明したカーティス-ヘドランド-リンドンの定理(英語版)の帰結である。可逆でない有限のセル・オートマトンには、どんな状態からも絶対生成(到達)できない配置が存在する。そのような配置を「エデンの園配置」と呼ぶ。換言すれば、エデンの園パターンにはプレイメージが存在しない。
1次元のセル・オートマトンについては、プレイメージを探すアルゴリズムが知られていて、各ルールについて可逆的かそうでないかは既に判明している。2次元以上のセル・オートマトンについては、任意のルールの可逆性は決定不能であることが証明されている。