セル・オートマトン（、略称：CA）とは、格子状のセルと単純な規則による、離散的計算モデルである。

計算可能性理論、数学、物理学、複雑適応系、数理生物学、微小構造モデリングなどの研究で利用される。非常に単純化されたモデルであるが、生命現象、結晶の成長、乱流といった複雑な自然現象を模した、驚くほどに豊かな結果を与えてくれる。

正確な発音に近いセルラ・オートマトンとも呼ばれることがある。セルは「細胞」「小部屋」、セルラは「細胞状の」、オートマトンは「からくり」「自動機械」を意味する。他に「セル空間」「埋め尽くしオートマトン」「」「」「」といった呼称もある。

 解説 
有限種類の（多くは2から数十種類の）状態を持つセル（細胞のような単位）によってセル・オートマトンは構成され、離散的な時間で個々のセルの状態が変化する。その変化は、ある時刻 t においてのセルの状態、および近傍のセルの内部状態によって、次の時刻t+1 、すなわち新たな「ジェネレーション」（世代）での各セルの状態が決定される。初期状態（時刻 t=0）は、各セルの状態を設定することで選択される。次の世代（t が1進んだ状態）は、事前に設定された「規則」（一般に何らかの数学的関数）に従って初期状態でのそのセルおよび近傍の状態から決定される。セルの状態を更新する規則は一般にどのセルでも同一であり、途中で変更されず、並んでいる全セルに同時に適用される。ただしや非同期セル・オートマトンは例外である。

その概念は1940年代、ロスアラモス国立研究所で同僚だったスタニスワフ・ウラムとジョン・フォン・ノイマンが発見した。その後細々と研究されていたが、1970年代に2次元セル・オートマトンの一種ライフゲームが登場すると注目されるようになった。1980年代にはスティーブン・ウルフラムが1次元セル・オートマトンまたはを体系的に研究し、一部の規則群がチューリング完全であることを示した。彼が2002年に出版した A New Kind of Science では、セル・オートマトンが様々な科学の領域で応用できると主張している。

 概要 

2次元の(つまり面状の)セル・オートマトンの例として、無限に広がる方眼紙を考える。方眼紙のひとつのマス目がセルにあたる。それぞれのセルは「黒」と「白」の2つの内部状態をもつ。セルの「近傍」とは、そのセルの周辺のセル群であり、通常は隣接するセルを指す。近傍には、四方を近傍とすると八方を近傍とするという2種類の典型的な定義がある。前者はセル・オートマトンの考案者の名を冠しており、直交して接する4つのセルを近傍とする。後者はフォン・ノイマン近傍を含み、さらに斜め方向の4つのセルも加えた中心のセルを囲む8つのセルの状態を考慮する。ムーア近傍の場合、それら9つのセルが取ることができる状態は全部で29 = 512個存在する。セル・オートマトンの時間発展の様子を表すルールは表で与えられる。すなわち次の時間ステップ（ t+1 ）で、中心のセルが「黒」「白」いずれになるかは、現在の時間ステップ（ t ）でとり得る512個のパターンそれぞれについての一覧表により決定される。ライフゲームはこのモデルの有名な例である。もう1つのよく知られている近傍の定義として「拡張フォン・ノイマン近傍」があり、直交する4方向それぞれの最も近い2つのセルを近傍とし、全部で8つのセルを近傍とする。セルがとりうる状態数を k、次の状態を決定するのに使われる近傍のセル数（自身も含める場合がある）を s とすると、このようなシステムの規則は kks という式で表される。したがって2次元のシステムでムーア近傍の場合、考えられるオートマトンの総数は 229 または となる。

例えば1次元セル・オートマトンでは、時刻（ステップ）を t、位置を1次元の i としたとき、セル xit の近傍は {xi−1t−1, xit−1, xi+1t−1} となる。

2次元のセル・オートマトンで最も有名なものがライフゲームである。ライフゲームは以下のようなルールで記述される。
 誕生: 死んでいるセル（「白」）の周囲に3つの生きているセル（「黒」）があれば次の時間ステップでは生きる（「黒」になる）。 
 維持: 生きているセル（「黒」）の周囲に2つか3つの生きているセル（「黒」）があれば次の世代でも生き残る（「黒」のままである）。 
 死亡: 上以外の場合には次の世代では死ぬ（「白」になる）。
このライフゲームのルールは細菌などの生物の繁殖のアナロジーである。すなわち、孤独でも人口過密でも死んでしまう。最も快適な人口密度では子孫を残し繁栄する性質を持つ。実際、ライフゲームは生物の増殖のような複雑で多様な振舞いを示す。

一般に各セルは同じ状態から開始し、一部の有限個のセルだけがそれ以外の状態から開始する。これを「コンフィギュレーション」と呼ぶ。また、全体が周期的なパターンを形成し、一部がそのパターンから外れた状態で開始する場合もある。後者は1次元のセル・オートマトンでは一般的である。

多くのセル・オートマトンのシミュレーションでは有限の格子を使う。2次元の場合、無限の平面ではなく、有限の四角形で表される。有限の格子での明らかな問題は端のセルの扱いであり、端のセルの扱いが格子全体のセルの状態に影響を与えるため重要な問題である。1つの手法は、端のセルを全て変化しない定数を状態として持つとする手法である。別の手法は端のセルの近傍を一般のセルとは違う内容にする手法である。つまり、端のセルの近傍を通常より少なく定義できるが、その場合は規則も新たに定義する必要がある。別の手法として、2次元の場合に四角形の平面の端の上下と左右を繋げて、トーラス形にする手法もある。これは、ある意味で無限の平面が同じ四角形で平面充填されている状態に近い。1次元であれば、線の端を繋いでループにする空間に相当する。これは端の問題を回避するために行うが、モジュロ演算関数を使って容易にプログラム可能という利点もある。

 歴史 

1940年代にロスアラモス国立研究所で働いていたスタニスワフ・ウラムは結晶の成長について研究していたとき、モデルとして単純な格子ネットワークを使用していた。同じころロスアラモスで一緒に働いていたジョン・フォン・ノイマンは自己複製機械を研究していた。フォン・ノイマンはまず、あるロボットの記述に基づいて別のロボットの記述を行うという設計を考えていた。この設計は運動学モデル（Kinematic model）と呼ばれている。設計を進めるに連れ、フォン・ノイマンは、複製を作るための「部品の海」をロボットに与えることのコストの膨大さやあるロボットが別のロボットを作るということを記述する大変さを徐々に理解していった。ノイマンは1948年の Hixon Symposium にて "The general and logical theory of automata" と題した論文を読む。またウラムはフォン・ノイマンに自己複製の還元主義的モデルとして離散系を使ってはどうかと示唆した。Nils Aall Barricelli はそういったモデルを使って人工生命を研究していた。

1950年代、ウラムとノイマンは液体の動きを計算する方法を生み出した。その中心となった考え方は液体を離散的単位の集まりとみなすということで、各単位の動作をその近傍の挙動に基づいて計算する。それらが元となってセル・オートマトンが生まれた。ウラムの格子ネットワークのように、は2次元で、その中に自己複製機械がアルゴリズム的に埋め込まれた。これがであり、近傍として隣接する4つのセルのみ（ノイマン近傍）を考慮し、1つのセルあたり29の内部状態を持っている。このモデルで彼は自己複製機械として動作するパターンを20万個のセルを使ってデザインし、それが無限に自己複製を繰り返すことを数学的に証明した。この設計は平面充填モデルとして知られている。1968年、エドガー・F・コッドは 8 状態で自己複製を繰り返すコッドのセル・オートマトンを考案している。

同じく1940年代、ノーバート・ウィーナーとがセル・オートマトンを開発しのモデルに採用した。その具体的な目的は、心筋におけるインパルス伝導の数学的説明であった。その業績は不整脈や興奮性媒質についての後の研究でよく引用されている。

1960年代、セル・オートマトンは力学系の特殊形として研究され、数学の一分野であると関連して研究され始めた。1969年、はその観点で数多くの成果をまとめ、それがセル・オートマトンの数学的研究における重要な論文とされている。

1969年、ドイツのコンピュータのパイオニアの1人であるコンラート・ツーゼは、著書 Calculating Space の中で、宇宙の物理法則は本質的には離散的であり、宇宙全体が一種の巨大なセル・オートマトン上の決定的な計算の結果であると主張した。この著書が今日デジタル物理学と呼ばれている分野の基礎を築いた。

1970年代、2状態で2次元のセル・オートマトンであるライフゲームが特にコンピュータコミュニティでよく知られるようになった。ジョン・コンウェイの発明によるもので、マーティン・ガードナーがサイエンティフィック・アメリカン誌（日本では日経サイエンス誌）で紹介したことで有名となったのである。ライフゲームは単純だが、システムとして興味深い挙動を示し、ランダム性と規則性の間で変動する。ライフゲームの最も顕著な特徴として「グライダー」（格子を横断して移動していくセル群）が頻繁に発生することが挙げられる。グライダーをうまく配置すると一種の相互作用が生まれる。長年の研究により、ライフゲームがチューリングマシンをエミュレートできることが判明した。それが単なる趣味の話題と受け止められたためか、ライフゲームの特殊性の研究や関連する規則の研究が若干行われた以外、この発見を受けた研究はなされなかった。

1981年、熱力学第二法則に反するように見える自然界の様々な複雑なパターンを検討していたスティーブン・ウルフラムは、セル・オートマトンの研究を始めた。当初の動機はセル・オートマトンで神経ネットワークなどのシステムをモデリングできるのではないかというものだった。1983年6月、Reviews of Modern Physics 誌にて（特にルール30）についての最初の論文を発表。ウルフラムは、単純な規則で示される振る舞いの予期せぬ複雑さを見て、自然界の複雑さも同様の機構によって生まれているのではないかと考えた。しかし、彼の研究によってセル・オートマトンは神経ネットワークのモデリングには貧弱すぎることが判明した。さらにウルフラムは真の無作為性との概念を定式化し、がチューリング完全であると推測した（1990年代にウルフラムの助手 Matthew Cook がそれを証明した）。

ウルフラムは1980年代中盤以降に学界を去ってMathematicaを開発し、彼のそれまでの研究結果を広い範囲の単純で抽象的な系に拡張して適用するのに Mathematica を使った。2002年、ウルフラムはそれらの成果を1280頁の著書 A New Kind of Science として発表した。この中でセル・オートマトンがあらゆる科学にとって重要な関わりを持つことを主張している。一部で誤解されているように、同書は物理法則がセル・オートマトンに基づいているとは言っていない（ツーゼとは異なる）が、セル・オートマトンに基づいた物理モデルをいくつか記述しており、他にも各種抽象系に基づいたモデルを示している。

 分類 
ウルフラムはあらゆる1次元のセル・オートマトンの時間発展の仕方を調べ上げ、セル・オートマトンを含む単純な計算モデルの4つのクラスを定義した。それまでのセル・オートマトンの研究では、パターンの種類から規則群を分類する傾向があったのに対して、ウルフラムの分類は規則自体を分類する最初の試みだった。4つのクラスは次の通りである。
 クラス1 - 秩序状態。ほぼ全ての初期状態で素早く安定した均質な状態になる。初期状態に無作為性があっても消滅する。
 クラス2 - 周期状態。ほぼ全ての初期状態で素早く安定状態または周期的に振動する状態になる。初期状態の無作為性は消滅する場合もあるが、残存する場合もある。初期状態を部分的に変更した場合、その影響は局所的となる傾向がある。
 クラス3 - カオス状態。ほぼ全ての初期状態でセル全体がランダムな変化を続ける。安定した構造が現れても、すぐに周囲のノイズによって破壊される。初期状態の部分的変更は全体に拡散していく傾向がある。
 クラス4 - ほぼ全ての初期状態で規則的なパターンとランダムなパターンが共存し、複雑なパターンを形成する。局所的に形成された構造は長期間存続することができる。
秩序状態であるクラス1、クラス2は新しい変化を生み出さない、いわば死んだ世界である。カオス状態であるクラス3はランダムすぎて、意味のある情報を生み出すことができない。ウルフラムは秩序状態とカオス状態の間にあるクラス4の様な状態こそが、生命現象などの現実世界で見られる複雑な現象を引き起こす源だと考えた。この研究により、複雑系と呼ばれる新しい科学分野の基盤が確立した。

これらの定義は質的なもので、その解釈には若干の幅がある。ウルフラムは「どんな一般分類体系でも、ある定義ではこのクラスになるが、別の定義では別のクラスになるというケースが必然的に存在する。セル・オートマトンでもそれは変わらない。あるクラスの特徴と別のクラスの特徴を備えた規則群は時として存在する」としている。ウルフラムの分類は、セル・オートマトンの出力を圧縮した長さの分類と経験的に合致している。

CulikとYuによって、ウルフラムの4つのクラスの算術的階層における位置が証明されている。クラス1と2は-完全、クラス3は-完全に所属する。

ウルフラムの分類に触発され、CAを形式的に厳密に分類しようとする試みもなされてきた。例えば、CulikとYuは3つのwell-definedなクラス（そしてそれらのどれにも分類されない4番目のクラス）を提案した。これを Culik-Yu クラスなどと呼び、ある規則群がどのクラスに属するかの判定は決定不能だと証明された。

 可逆型 
現在状態から1つ前の状態（プレイメージ）が一意に求められるセル・オートマトンを「可逆的」(reversible) であるという。セル・オートマトンを状態から状態への関数と考えると、可逆性はその関数が全単射であることを意味する。可逆型のセル・オートマトンは、時間を遡った際の挙動もセル・オートマトンとして記述できる。これは、セル・オートマトンを位相幾何学的に説明したの帰結である。可逆でない有限のセル・オートマトンには、どんな状態からも絶対生成（到達）できない配置が存在する。そのような配置を「エデンの園配置」と呼ぶ。換言すれば、エデンの園パターンにはプレイメージが存在しない。

1次元のセル・オートマトンについては、プレイメージを探すアルゴリズムが知られていて、各ルールについて可逆的かそうでないかは既に判明している。2次元以上のセル・オートマトンについては、任意のルールの可逆性は決定不能であることが証明されている。Jarkko Kari による証明は、ワンのタイルのタイル並べ問題と関連している。

可逆型セル・オートマトンは、熱力学の法則に従う気体や液体の力学現象のシミュレーションに使われることが多い。その場合のセル・オートマトンは特別に可逆性を持つよう設計される。この種のシステムの研究者としてトマソ・トフォリやらがいる。意識的に可逆型セル・オートマトンを作る手法はいくつか存在する。やがそれで、どちらもセル・オートマトンの定義に何らかの修正を施す。これらは厳密には上に挙げたようなセル・オートマトンの定義から外れているが、十分に大きな近傍と多数の状態を持つ従来型のセル・オートマトンでエミュレートできることが判っており、従来型のセル・オートマトンのサブセットと見なすことができる。逆に全ての可逆型セル・オートマトンはブロック・セル・オートマトンでエミュレートできる。

 総和型 
特殊なセル・オートマトンとして、総和型 (totalistic) セル・オートマトンがある。総和型セル・オートマトンでの各セルの状態は数値で表され（通常、有限個の整数値）、時刻 t におけるセルの値は、時刻 t−1 における近傍（自身も含むこともある）のセル群の値の総和だけに依存して決定される。時刻 t におけるセルの状態が自身の t−1 での状態に依存する場合、そのようなセル・オートマトンを「外部総和型」(outer totalistic) と呼ぶ。ライフゲームは、値として 0 と 1 をとる外部総和型のセル・オートマトンの例である。同じく外部総和型でムーア近傍だが、規則をライフゲームとは変えたセル・オートマトンを欧米では "life-like" と呼ぶ。