Cellular Automata
「ライフゲーム」に代表されるような、ドット絵が一定のルールに従って刻々と変化していくモデル。フォン・ノイマンが機械による自己増殖の可能性を研究する目的で考案したものが最初のもの。
一般的には碁盤目のような格子点がそれぞれ整数の値を持っていて、現在の自分の値と隣接する格子点での値から一定のルールによって次の時間ステップでの値が計算され、すべての格子点で一斉に更新される。
単純なルールでも複雑なパターンが出現する場合がある。特に一次元で値が0と1しかないような場合でも、ルールを選べばチューリングマシンをエミュレートできる。チューリングマシンにある問題を計算させた場合に計算が有限時間で終わるかどうかをあらかじめ予測することは出来ないので、このセル・オートマトンもどのようなパターンに落ち着くかは予測できないことになる。
Mathematica を作ったスティーブン・ウォルフラムはもともとセル・オートマトンの研究をしていた。