セルラーオートマトンとは、コンピュータサイエンスや数学で使われるモデルの一つです。多数のセル（格子上の離散単位）を並べ、それぞれが有限個の状態を取り、離散的な時間ステップごとに全セルの状態が同時に更新されることで、空間と時間にまたがる動的な系を表現します。各セルの次の状態は、そのセル自身の現在の状態と近傍（隣接するセル）の状態に基づく「規則（ルール）」によって決定されます。これにより、単純な局所ルールから複雑で予測しにくいマクロな振る舞い（複雑性や自己組織化）が現れます。
仕組み（定義と更新ルール）
- 格子とセル：セルラーオートマトンは1次元、2次元、さらには高次元の格子上で定義できます。各格子点が「セル」で、各セルは有限個の状態（例：0/1やいくつかの色）を持ちます。
- 近傍（ナイバーフッド）：各セルの更新に参照される周囲のセル集合を近傍と呼びます。代表的な近傍は、1次元で両隣を含むもの、2次元でのフォン・ノイマン近傍（上下左右4近傍）やムーア近傍（8近傍）です。
- 更新ルール：有限の入力（近傍の状態）に対して各出力（次の状態）が決まる決定論的ルールが一般的です。ルールは全てのセルに同じように適用され、通常は全セルを同時に一斉更新（同期）します。確率的に更新する確率的セルオートマトンや、非同期更新を許す変種もあります。
- 境界条件：有限格子では端での扱い（固定境界、反射、トーラス状の周期境界など）を定めます。境界条件によって挙動が変わることがあります。
代表例：コンウェイのライフゲーム（Game of Life）
セルラーオートマトンの最も有名な例が、英国の数学者ジョン・ホートン・コンウェイによる「ライフゲーム」です（1970年代に普及）。ライフゲームは2次元のムーア近傍（8近傍）を使い、各セルは生（1）か死（0）の二値状態を取ります。ルールは簡潔にB3/S23と表されます：
- 誕生（Birth）B3：死んでいるセルは、周囲にちょうど3つの生セルがあれば生になる。
- 生存（Survival）S23：生きているセルは、周囲に2または3つの生セルがいれば次も生き残る。そうでなければ死ぬ（過疎または過密）。
ライフゲームは単純なルールから多様なパターン（グライダー、静止形（スティルライフ）、振動子、宇宙船、ガンなど）が出現し、計算可能性（チューリング完全性）や自己複雑化の例として研究されています。
歴史的背景
セルラーオートマトンの原型的なアイデアは20世紀中頃に現れました。1940年代にはスタニスワフ・ウラムやジョン・フォン・ノイマンが自己複製機構や離散モデルの研究を行い、セルラーオートマトンの理論的基盤を築きました。1970年代にコンウェイのライフゲームが広く知られるようになり、以後、スティーブン・ウルフラムらによる1次元セルオートマトンの系統的研究や、計算理論・複雑系としての発展が続きました。
種類と理論的特徴
- 1次元セルオートマトン：各セルが左・自身・右など限られた近傍を参照する単純モデル。ウルフラムのルール番号（0〜255）で代表される。
- 2次元セルオートマトン：ライフゲームのように平面格子上で振る舞う。複雑で視覚的にわかりやすいパターンが出現することが多い。
- 確率的・連続値セルオートマトン：状態が確率的に変化する場合や、状態が連続値をとる拡張もある（連続セルオートマトンは差分方程式に近い振る舞いを示す）。
- 可逆セルオートマトン：時間を逆にたどれるルール（可逆写像）を持つもの。保存則や物理的可逆性の研究に重要。
- 計算能力：いくつかのセルオートマトン（ライフゲームを含む）はチューリング完全であり、任意の計算を模擬できることが示されています。
応用例
- 複雑系・自己組織化の研究（物理、化学、生物の模擬）
- 都市交通や群集の流れ、森林火災の拡散などのシミュレーション
- ランダム数生成や暗号の一部要素（特定のセルオートマトンの振る舞いを利用）
- 並列計算やハードウェア実装（局所ルールの並列適用が容易なため）
- 教育や可視化（単純な規則から複雑性が生じることを示す教材）
観察される現象と研究トピック
- 局所ルールからの巨視的秩序：単純な局所相互作用が複雑なパターンや長期的構造を生む。
- 相転移と臨界現象：ルールやパラメータを変えると、秩序的・無秩序的・複雑的な相に遷移することがある。
- 分類と普遍性：ウルフラムのクラス分類（クラス1〜4）や、どの条件で計算普遍性が現れるかの研究。
まとめ
セルラーオートマトンは、単純で局所的な更新規則によって時間発展する格子系の枠組みです。ライフゲームのような直感的で視覚的な例から、理論的に深い計算可能性や物理的意味を持つモデルまで幅広く含み、研究・教育・応用の両面で重要な役割を果たしています。
