セルオートマトン

セル(細胞)状になっているオートマトン。代表的な例にライフゲームがある。

各セルはそれぞれ特定の状態を示しており、状態の推移に対してルールが定められている。このルールに基づいて自動的にセルの状態を連鎖的に更新していくオートマトンがセルオートマトン(CA)である。

非常に単純で小さいルール(隣接したセル間など局所的なルールでのみ相互作用する)を超並列に集合させることで巨大で複雑な事象をシミュレートすることができるという特徴がある。このため生体の組織形成や自然現象のモデル化などでよく応用される。時間・空間・各セル間において離散的なシステムで、並列処理環境に向き計算も速いが、格子が有限である限りセルオートマトンの情報も有限であり、セル状態が離散的なためにセルオートマトンで情報を作ることはできないという欠点もある。またシミュレーションを行なう際には膨大な格子数が必要で、処理システムのリソース量に大きく影響する。

最初に体系化されたセルオートマトンは1940年代末に生物の自己再製機能をシミュレートするために、数学者のウラム(モンテカルロ法の開発者)とジョン・フォン・ノイマン(ゲーム理論の創始者、ノイマン型電子計算機の設計者)によって開発された提唱された。フォン・ノイマンはオートマトンが自分自身のレプリカを作ることができるかという研究において、自己再製には機械自身が自己の設計図(ブループリント)を有しその設計図を再製できれば自己の複製もできる、と結論づけた。これに対してウラムが理論のシミュレートに機械でなく有限状態数を持つセル空間によるモデル構造を使うことを示唆し、フォン・ノイマンがこれを受けて自己再製するセル状のオートマトンの記述を1952(昭和27)年に完成させた。フォン・ノイマンのオートマトンは29種の状態をとるが、この後、8種のコッドのオートマトンやたった2種しかとらないライフゲームの他、エドワード・フレドキンによるフレドキン・ルール(フォン・ノイマンのものより遥かに単純な自己再製オートマトンのルール)の発見、1980年代半ばのウルフラムによるウルフラムクラス(一次元セルオートマトンの4パターンのクラス分け)の定義による統計的解釈、ラングトンによるλパラメーター(秩序からカオスへの相転移が起きるときのセル遷移状態の確率値)の発見と人工生命(ALife)研究の創始、などの発展があり、これらの研究は今日も続いている。

セルオートマトンの欠点である、セル状態が離散的であるためにセルオートマトン自体から情報を作れないこととカオス的現象を表現できないことに対応した、カオスセルオートマトン(CCA: Chaos Cellular Automaton)というモデルもある。このモデルではセル状態が連続的に更新できるようにされている。時間・空間は通常のセルオートマトンと同様に離散的であるため微分方程式モデルに比べ統計学的に扱いやすく、またルール変更によって各種時空間での複雑なモデルを容易に構築できセルオートマトンと違ってセル数を膨大に取らなくてもシミュレーションできるという実用的な特徴がある。生命現象や自然現象、社会現象の分野で応用されている。

通信用語の基礎知識検索システム WDIC Explorer Version 7.04a (27-May-2022)