セル・オートマトン
セルがとりうる状態数を k、次の状態を決定するのに使われる近傍のセル数(自身も含める場合がある)を s とすると、このようなシステムの規則は k という式で表される。したがって2次元のシステムでムーア近傍の場合、考えられるオートマトンの総数は 2 または 1.34×10 となる。
例えば1次元セル・オートマトンでは、時刻(ステップ)を t、位置を1次元の i としたとき、セル xi の近傍は {xi−1, xi, xi+1} となる。
2次元のセル・オートマトンで最も有名なものがライフゲームである。ライフゲームは以下のようなルールで記述される。
誕生: 死んでいるセル(「白」)の周囲に3つの生きているセル(「黒」)があれば次の時間ステップでは生きる(「黒」になる)。
維持: 生きているセル(「黒」)の周囲に2つか3つの生きているセル(「黒」)があれば次の世代でも生き残る(「黒」のままである)。
死亡: 上以外の場合には次の世代では死ぬ(「白」になる)。
このライフゲームのルールは細菌などの生物の繁殖のアナロジーである。すなわち、孤独でも人口過密でも死んでしまう。最も快適な人口密度では子孫を残し繁栄する性質を持つ。実際、ライフゲームは生物の増殖のような複雑で多様な振舞いを示す。
ルール30は、ブロック暗号に応用可能という提案がある。
セル・オートマトンを公開鍵暗号に使うという提案もある。
ウルフラムはあらゆる1次元のセル・オートマトンの時間発展の仕方を調べ上げ、セル・オートマトンを含む単純な計算モデルの4つのクラスを定義した。それまでのセル・オートマトンの研究では、パターンの種類から規則群を分類する傾向があったのに対して、ウルフラムの分類は規則自体を分類する最初の試みだった。4つのクラスは次の通りである。
クラス1 - 秩序状態。ほぼ全ての初期状態で素早く安定した均質な状態になる。初期状態に無作為性があっても消滅する。
クラス2 - 周期状態。ほぼ全ての初期状態で素早く安定状態または周期的に振動する状態になる。初期状態の無作為性は消滅する場合もあるが、残存する場合もある。初期状態を部分的に変更した場合、その影響は局所的となる傾向がある。
クラス3 - カオス状態。ほぼ全ての初期状態でセル全体がランダムな変化を続ける。安定した構造が現れても、すぐに周囲のノイズによって破壊される。初期状態の部分的変更は全体に拡散していく傾向がある。
クラス4 - ほぼ全ての初期状態で規則的なパターンとランダムなパターンが共存し、複雑なパターンを形成する。局所的に形成された構造は長期間存続することができる。
秩序状態であるクラス1、クラス2は新しい変化を生み出さない、いわば死んだ世界である。カオス状態であるクラス3はランダムすぎて、意味のある情報を生み出すことができない。
Jarkko Kari による証明は、ワンのタイルのタイル並べ問題と関連している。
可逆型セル・オートマトンは、熱力学の法則に従う気体や液体の力学現象のシミュレーションに使われることが多い。その場合のセル・オートマトンは特別に可逆性を持つよう設計される。この種のシステムの研究者としてトマソ・トフォリやノーマン・マーゴラス(英語版)らがいる。意識的に可逆型セル・オートマトンを作る手法はいくつか存在する。二階セル・オートマトン(英語版)やブロック・セル・オートマトン(英語版)がそれで、どちらもセル・オートマトンの定義に何らかの修正を施す。これらは厳密には上に挙げたようなセル・オートマトンの定義から外れているが、十分に大きな近傍と多数の状態を持つ従来型のセル・オートマトンでエミュレートできることが判っており、従来型のセル・オートマトンのサブセットと見なすことができる。逆に全ての可逆型セル・オートマトンはブロック・セル・オートマトンでエミュレートできる。