セル・オートマトンのソースを表示

[[ファイル:Gospers glider gun.gif|frame|right|セル・オートマトンの一種[[ライフゲーム]]で、{{仮リンク|ビル・ゴスパー|en|Bill Gosper|label=ゴスパー}}の[[グライダー銃]]が[[グライダー (ライフゲーム)|グライダー]]を放っているところ<ref>[[ダニエル・デネット|Daniel Dennett]] (1995), ''Darwin's Dangerous Idea'', Penguin Books, London, ISBN 978-0-14-016734-4, ISBN 0-14-016734-X</ref>]]

'''セル・オートマトン'''（{{lang-en-short|cellular automaton}}、略称：'''CA'''）とは、格子状のセルと単純な規則による、[[離散数学|離散的]]計算モデルである。[[計算可能性理論]]、[[数学]]、[[物理学]]、[[複雑適応系]]、[[数理生物学]]、微小構造モデリングなどの研究で利用される。非常に単純化されたモデルであるが、[[生命]]現象、[[結晶]]の成長、[[乱流]]といった複雑な[[自然現象]]を模した、驚くほどに豊かな結果を与えてくれる。

正確な発音に近い'''セルラ・オートマトン'''とも呼ばれることがある。セルは「[[細胞]]」「小部屋」、セルラは「細胞状の」、[[オートマトン]]は「からくり」「自動機械」を意味する。他に「セル空間」「埋め尽くしオートマトン」「{{lang|en|homogeneous structure}}」「{{lang|en|tessellation structure}}」「{{lang|en|iterative array}}」といった呼称もある<ref>{{Cite journal| url= http://www.stephenwolfram.com/publications/articles/ca/83-statistical/ | author=Wolfram, Stephen | authorlink=スティーブン・ウルフラム | title=Statistical Mechanics of Cellular Automata | journal=Reviews of Modern Physics | issue=3 | volume=55 | pages=601–644 | year=1983 | doi=10.1103/RevModPhys.55.601 | bibcode=1983RvMP...55..601W | ref=harv}}</ref>。

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

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

== 概要 ==
[[File:Vierer-Nachbarschaft.png|thumb|right|フォン・ノイマン近傍（DがPの近傍）]]
2次元の(つまり面状の)セル・オートマトンの例として、無限に広がる[[方眼紙]]を考える。方眼紙のひとつのマス目がセルにあたる。それぞれのセルは「黒」と「白」の2つの内部状態をもつ。セルの「近傍」とは、そのセルの周辺のセル群であり、通常は隣接するセルを指す。近傍には、{{仮リンク|フォン・ノイマン近傍|en|von Neumann neighborhood}}と{{仮リンク|ムーア近傍|en|Moore neighborhood}}という2種類の典型的な定義がある<ref name=kier-seybold-cheng-15>{{Harvnb|Kier|Seybold|Cheng|2005|p=15}}</ref>。前者はCAの考案者の名を冠しており、[[直交]]して接する4つのセルを近傍とする<ref name=kier-seybold-cheng-15/>。後者はフォン・ノイマン近傍を含み、さらに斜め方向の4つのセルも加えた中心のセルを囲む8つのセルの状態を考慮する<ref name=kier-seybold-cheng-15/>。ムーア近傍の場合、それら9つのセルが取ることができる状態は全部で2<sup>9</sup> = 512個存在する。セル・オートマトンがどのように時間発展していくかのルールは表として与えられる。すなわち次の時間ステップ(t+1)で、中心のセルが「黒」「白」いずれになるかは、現在の時間ステップ(t)でとり得る512個のパターンそれぞれについての一覧表によって決定される。[[ライフゲーム]]はこのモデルの有名な例である。もう1つのよく知られている近傍の定義として「拡張フォン・ノイマン近傍」があり、直交する4方向それぞれの最も近い2つのセルを近傍とし、全部で8つのセルを近傍とする<ref name=kier-seybold-cheng-15/>。セルがとりうる状態数を ''k''、次の状態を決定するのに使われる近傍のセル数（自身も含める場合がある）を ''s'' とすると、このようなシステムの規則は ''k''<sup>''k''<sup>''s''</sup></sup> という式で表される<ref name=bialynick-9>{{Harvnb|Bialynicki-Birula|Bialynicka-Birula|2004|p=9}}</ref>。したがって2次元のシステムでムーア近傍の場合、考えられるオートマトンの総数は 2<sup>2<sup>9</sup></sup> または {{Val|1.34|e=154}} となる。

例えば1次元セル・オートマトンでは、時刻（ステップ）を ''t''、位置を1次元の ''i'' としたとき、セル ''x<sub>i</sub><sup>t</sup>'' の近傍は {''x''<sub>''i''−1</sub><sup style="margin-left:-2ex;">''t''−1</sup>, ''x''<sub>''i''</sub><sup>''t''−1</sup>, ''x''<sub>''i''+1</sub><sup style="margin-left:-2ex;">''t''−1</sup>} となる。

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

一般に、各セルは同じ状態から開始し、一部の有限個のセルだけがそれ以外の状態から開始する。これを「コンフィギュレーション」と呼ぶ<ref name=schiff-41>{{Harvnb|Schiff|2011|p=41}}</ref>。また、全体が周期的なパターンを形成していて、一部がそのパターンから外れた状態で開始するということもある。後者は1次元のセル・オートマトンでは一般的である。

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

== 歴史 ==
[[ファイル:John von Neumann ID badge.png|left|thumb|upright|[[ロスアラモス国立研究所]]のIDバッジをつけた[[ジョン・フォン・ノイマン]]]]
1940年代に[[ロスアラモス国立研究所]]で働いていた[[スタニスワフ・ウラム]]は結晶の成長について研究していたとき、モデルとして単純な[[格子]]ネットワークを使用していた<ref name=pickover>{{Cite book| author=Pickover, Clifford A. | title=The Math Book: From Pythagoras to the 57th Dimension, 250 Milestones in the History of Mathematics | page=406 | year=2009| publisher=Sterling Publishing Company, Inc | isbn=978-1402757969}}</ref>。同じころロスアラモスで一緒に働いていた[[ジョン・フォン・ノイマン]]は[[自己複製]]機械を研究していた<ref name=schiff-1>{{Harvnb|Schiff|2011|p=1}}</ref>。フォン・ノイマンはまず、あるロボットの記述に基づいて別のロボットの記述を行うという設計を考えていた。この設計は運動学モデル（Kinematic model）と呼ばれている<ref>John von Neumann, “The general and logical theory of automata,” in L.A. Jeffress, ed., Cerebral Mechanisms in Behavior – The Hixon Symposium, John Wiley & Sons, New York, 1951, pp. 1-31.</ref><ref>John G. Kemeny, “Man viewed as a machine,” Sci. Amer. 192(April 1955):58-67; Sci. Amer. 192(June 1955):6 (errata).</ref>。設計を進めるに連れ、フォン・ノイマンは、複製を作るための「部品の海」をロボットに与えることのコストの膨大さやあるロボットが別のロボットを作るということを記述する大変さを徐々に理解していった。ノイマンは1948年の Hixon Symposium にて "The general and logical theory of automata" と題した論文を読む<ref name=schiff-1/>。またウラムはフォン・ノイマンに自己複製の還元主義的モデルとして離散系を使ってはどうかと示唆した<ref name=schiff-3>{{Harvnb|Schiff|2011|p=3}}</ref><ref name=ilachinski-xxix>{{Harvnb|Ilachinski|2001|p=xxix}}</ref>。[[:en:Nils Aall Barricelli|Nils Aall Barricelli]] はそういったモデルを使って[[人工生命]]を研究していた。

1950年代、ウラムとノイマンは液体の動きを計算する方法を生み出した。その中心となった考え方は液体を離散的単位の集まりとみなすということで、各単位の動作をその近傍の挙動に基づいて計算する<ref name=bialynick-8>{{Harvnb|Bialynicki-Birula|Bialynicka-Birula|2004|p=8}}</ref>。それらが元となってセル・オートマトンが生まれた。ウラムの格子ネットワークのように、フォン・ノイマンのセル・オートマトンは2次元で、その中に自己複製機械がアルゴリズム的に埋め込まれた。これが{{仮リンク|ユニバーサルコンストラクタ|en|Von Neumann universal constructor}}であり、近傍として隣接する4つのセルのみ（ノイマン近傍）を考慮し、1つのセルあたり29の内部状態を持っている<ref name=wolfram-876>{{Harvnb|Wolfram|2002|p=876}}</ref>。このモデルで彼は自己複製機械として動作するパターンを20万個のセルを使ってデザインし、それが無限に自己複製を繰り返すことを数学的に証明した<ref name=wolfram-876/>。この設計は[[平面充填]]モデルとして知られている<ref name=TSRA>{{Cite book| author=von Neumann, John | coauthors=Burks, Arthur W. | title=Theory of Self-Reproducing Automata | year=1966 | publisher=University of Illinois Press}}</ref>。[[1968年]]、[[エドガー・F・コッド]]は 8 状態で自己複製を繰り返す[[コッドのセル・オートマトン]]を考案している。

同じく1940年代、[[ノーバート・ウィーナー]]と{{仮リンク|アルトゥーロ・ローゼンブリュート|en|Arturo Rosenblueth}}がセル・オートマトンを開発し{{仮リンク|興奮性媒質|en|Excitable medium}}のモデルに採用した<ref>{{Cite journal| last1 = Wiener | first1 = N. | last2 = Rosenblueth | first2 = A. | year = 1946 | title = The mathematical formulation of the problem of conduction of impulses in a network of connected excitable elements, specifically in cardiac muscle | url = | journal = Arch. Inst. Cardiol. México | volume = 16 | issue = | page = 205 | ref = harv }}</ref>。その具体的な目的は、[[心筋]]におけるインパルス伝導の数学的説明であった。その業績は[[不整脈]]や興奮性媒質についての後の研究でよく引用されている<ref>{{Cite journal| doi = 10.1038/355349a0 | last1 = Davidenko | first1 = J. M. | last2 = Pertsov | first2 = A. V. | last3 = Salomonsz | first3 = R. | last4 = Baxter | first4 = W. | last5 = Jalife | first5 = J. | year = 1992 | title = Stationary and drifting spiral waves of excitation in isolated cardiac muscle | url = | journal = Nature | volume = 355 | issue = 6358| pages = 349–351 | pmid = 1731248 |bibcode = 1992Natur.355..349D | ref = harv }}</ref>。

1960年代、セル・オートマトンは[[力学系]]の特殊形として研究され、数学の一分野である{{仮リンク|記号力学|en|symbolic dynamics}}と関連して研究され始めた。1969年、{{仮リンク|グスタフ・A・ヘドランド|en|Gustav A. Hedlund}}はその観点で数多くの成果をまとめ<ref>{{Cite journal| doi = 10.1007/BF01691062 | last1 = Hedlund | first1 = G. A. | year = 1969 | title = Endomorphisms and automorphisms of the shift dynamical system | url = http://www.springerlink.com/content/k62915l862l30377/ | journal = Math. Systems Theory | volume = 3 | issue = 4| pages = 320–3751 | ref = harv }}</ref>、それがセル・オートマトンの数学的研究における重要な論文とされている。

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

[[1970年代]]、2状態で2次元のセル・オートマトンである[[ライフゲーム]]が特にコンピュータコミュニティでよく知られるようになった。[[ジョン・ホートン・コンウェイ|ジョン・コンウェイ]]の発明によるもので、[[マーティン・ガードナー]]が[[サイエンティフィック・アメリカン]]誌（日本では[[日経サイエンス]]誌）で紹介したことで有名となったのである<ref>{{Cite journal| last1 = Gardner | first1 =Martin | year = 1970 | title = Mathematical Games: The fantastic combinations of John Conway's new solitaire game "life" | url = http://www.ibiblio.org/lifepatterns/october1970.html | journal = Scientific American | issue = 223 | pages = 120–123 | ref = harv }}</ref>。ライフゲームは単純だが、システムとして興味深い挙動を示し、[[ランダム]]性と規則性の間で変動する。ライフゲームの最も顕著な特徴として「グライダー」（格子を横断して移動していくセル群）が頻繁に発生することが挙げられる。グライダーをうまく配置すると一種の相互作用が生まれる。長年の研究により、ライフゲームが[[チューリングマシン]]をエミュレートできることが判明した<ref>Paul Chapman. [http://www.igblan.free-online.co.uk/igblan/ca/ Life universal computer]. November 2002</ref>。それが単なる趣味の話題と受け止められたためか、ライフゲームの特殊性の研究や関連する規則の研究が若干行われた以外、この発見を受けた研究はなされなかった。

1981年、[[熱力学第二法則]]に反するように見える自然界の様々な複雑なパターンを検討していた[[スティーブン・ウルフラム]]は、セル・オートマトンの研究を始めた<ref name=wolfram-880/>。当初の動機はセル・オートマトンで神経ネットワークなどのシステムをモデリングできるのではないかというものだった<ref name=wolfram-880/>。1983年6月、''[[:en:Reviews of Modern Physics|Reviews of Modern Physics]]'' 誌にて{{仮リンク|基本セル・オートマトン|en|elementary cellular automaton}}（特に{{仮リンク|ルール30|en|Rule 30}}）についての最初の論文を発表<ref name=wolfram-880>{{Harvnb|Wolfram|2002|p=880}}</ref>。ウルフラムは、単純な規則で示される振る舞いの予期せぬ複雑さを見て、自然界の複雑さも同様の機構によって生まれているのではないかと考えた<ref name=wolfram-880/>。しかし、彼の研究によってセル・オートマトンは神経ネットワークのモデリングには貧弱すぎることが判明した<ref name=wolfram-880/>。さらにウルフラムは真の[[ランダム|無作為性]]と{{仮リンク|計算既約性|en|computational irreducibility}}の概念を定式化し<ref name=wolfram-881>{{Harvnb|Wolfram|2002|p=881}}</ref>、{{仮リンク|ルール110|en|rule 110}}が[[チューリング完全]]であると推測した（1990年代にウルフラムの助手 [[:en:Matthew Cook|Matthew Cook]] がそれを証明した）。

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

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

これらの定義は質的なもので、その解釈には若干の幅がある。ウルフラムは「どんな一般分類体系でも、ある定義ではこのクラスになるが、別の定義では別のクラスになるというケースが必然的に存在する。セル・オートマトンでもそれは変わらない。あるクラスの特徴と別のクラスの特徴を備えた規則群は時として存在する」としている<ref name=wolfram-231>{{Harvnb|Wolfram|2002|p=231}}</ref>。ウルフラムの分類は、セル・オートマトンの出力を圧縮した長さの分類と経験的に合致している<ref>{{Cite journal |last=Zenil |first=Hector |title=Compression-based investigation of the dynamical properties of cellular automata and other systems |journal=Complex Systems |year=2010 |volume=19 |issue=1 |url= http://www.complex-systems.com/pdf/19-1-1.pdf}}</ref>。

CulikとYuによって、ウルフラムの4つのクラスの[[算術的階層]]における位置が証明されている。クラス1と2は<math>\Pi^0_2</math>-完全、クラス3は<math>\Sigma^0_3</math>-完全に所属する。

ウルフラムの分類に触発され、CAを形式的に厳密に分類しようとする試みもなされてきた。例えば、CulikとYuは3つの[[well-defined]]なクラス（そしてそれらのどれにも分類されない4番目のクラス）を提案した。これを Culik-Yu クラスなどと呼び、ある規則群がどのクラスに属するかの判定は[[決定可能性|決定不能]]だと証明された<ref name="DelormeMazoyer1998">{{Cite book |editor=M. Delorme, J. Mazoyer |title=Cellular automata: a parallel model |url= http://books.google.com/books?id=dGs87s5Pft0C&pg=PA239 |year=1998 |publisher=Springer |isbn=978-0-7923-5493-2 |page=239 |chapter=Topological chaos and CA |author=G. Cattaneo, E. Formenti, L. Margara}}</ref><ref name="Voorhees1996">{{Cite book |author=Burton H. Voorhees |title=Computational analysis of one-dimensional cellular automata |url= http://books.google.com/books?id=WcZTQHPrG68C&pg=PA8 |year=1996 |publisher=World Scientific |isbn=978-981-02-2221-5 |page=8}}</ref><ref name="Garzon1995">{{Cite book |author=Max Garzon |title=Models of massive parallelism: analysis of cellular automata and neural networks |year=1995 |publisher=Springer |isbn=978-3-540-56149-1 |page=149}}</ref>。

=== 可逆型 ===
現在状態から1つ前の状態（プレイメージ）が一意に求められるセル・オートマトンを「[[可逆計算|可逆的]]」(reversible) であるという<ref name=kari-379>{{Harvnb|Kari, Jarrko|1991|p=379}}</ref>。セル・オートマトンを状態から状態への関数と考えると、可逆性はその関数が[[全単射]]であることを意味する<ref name=kari-379/>。可逆型のセル・オートマトンは、時間を遡った際の挙動もセル・オートマトンとして記述できる。これは、セル・オートマトンを位相幾何学的に説明した{{仮リンク|カーティス-ヘドランド-リンドンの定理|en|Curtis–Hedlund–Lyndon theorem}}の帰結である<ref>{{Cite journal |first=D. |last=Richardson |title=Tessellations with local transformations |journal=J. Computer System Sci. |volume=6 |year=1972 |pages=373–388 |issue=5 |doi=10.1016/S0022-0000(72)80009-6 |ref=harv}}</ref><ref>{{Cite book |title=Cellular Automata in Hyperbolic Spaces - Tome I, Volume 1 |first=Maurice|last=Margenstern |publisher=Archives contemporaines |year=2007 |isbn=978-2-84703-033-4 |page=134 |url= http://books.google.com/books?id=wGjX1PpFqjAC&pg=PA134 |ref=harv}}</ref>。可逆でない有限のセル・オートマトンには、どんな状態からも絶対生成（到達）できない配置が存在する。そのような配置を「[[エデンの園配置]]」と呼ぶ<ref name=schiff-103>{{Harvnb|Schiff|2011|p=103}}</ref>。換言すれば、エデンの園パターンにはプレイメージが存在しない。

1次元のセル・オートマトンについては、プレイメージを探すアルゴリズムが知られていて、各ルールについて可逆的かそうでないかは既に判明している<ref>Serafino Amoroso, Yale N. Patt, ''Decision Procedures for Surjectivity and Injectivity of Parallel Maps for Tessellation Structures''. J. Comput. Syst. Sci. 6(5): 448-464 (1972)</ref><ref>{{Cite journal |journal=Complex Systems |volume=5 |year=1991 |pages=19–30 |title=De Bruijn Graphs and Linear Cellular Automata |first=Klaus |last=Sutner |url= http://www.complex-systems.com/pdf/05-1-3.pdf|ref=harv}}</ref>。2次元以上のセル・オートマトンについては、任意のルールの可逆性は[[決定可能性|決定不能]]であることが証明されている。[[:en:Jarkko Kari|Jarkko Kari]] による証明は、{{仮リンク|ワンのタイル|en|Wang tile}}のタイル並べ問題と関連している<ref>{{Cite journal |first=Jarkko |last=Kari |title=Reversibility of 2D cellular automata is undecidable |journal=Physica D |volume=45 |year=1990 |pages=379–385 |doi=10.1016/0167-2789(90)90195-U |bibcode = 1990PhyD...45..379K |ref=harv}}</ref>。

可逆型セル・オートマトンは、[[熱力学]]の法則に従う気体や液体の力学現象のシミュレーションに使われることが多い。その場合のセル・オートマトンは特別に可逆性を持つよう設計される。この種のシステムの研究者として[[トマソ・トフォリ]]や{{仮リンク|ノーマン・マーゴラス|en|Norman Margolus}}らがいる。意識的に可逆型セル・オートマトンを作る手法はいくつか存在する。{{仮リンク|二階セル・オートマトン|en|second order cellular automaton}}や{{仮リンク|ブロック・セル・オートマトン|en|block cellular automaton}}がそれで、どちらもセル・オートマトンの定義に何らかの修正を施す。これらは厳密には上に挙げたようなセル・オートマトンの定義から外れているが、十分に大きな近傍と多数の状態を持つ従来型のセル・オートマトンでエミュレートできることが判っており、従来型のセル・オートマトンのサブセットと見なすことができる。逆に全ての可逆型セル・オートマトンはブロック・セル・オートマトンでエミュレートできる<ref>{{Cite journal |title=On the circuit depth of structurally reversible cellular automata |first=Jarkko |last=Kari |journal=Fundamenta Informaticae |volume=38 |year=1999 |pages=93–107 |ref=harv}}</ref><ref>{{Cite journal |title=Representing reversible cellular automata with reversible block cellular automata |last=Durand-Lose |first=Jérôme |journal=Discrete Mathematics and Theoretical Computer Science |volume=AA |year=2001 |pages=145–154 |ref=harv}}</ref>。

=== 総和型 ===
特殊なセル・オートマトンとして、総和型 (totalistic) セル・オートマトンがある。総和型セル・オートマトンでの各セルの状態は数値で表され（通常、有限個の整数値）、時刻 ''t'' におけるセルの値は、時刻 ''t''&minus;1 における近傍（自身も含むこともある）のセル群の値の総和だけに依存して決定される<ref name=wolfram-60>{{Harvnb|Wolfram|2002|p=60}}</ref><ref name="cadu">{{Cite book |title=Cellular automata: a discrete universe |first=Andrew |last=Ilachinski |publisher=World Scientific |year=2001 |isbn=978-981-238-183-5 |pages=44–45 |url= http://books.google.com/books?id=3Hx2lx_pEF8C&pg=PA4 |ref=harv}}</ref>。時刻 ''t'' におけるセルの状態が自身の ''t''&minus;1 での状態に依存する場合、そのようなセル・オートマトンを「外部総和型」(outer totalistic) と呼ぶ<ref name="cadu"/>。[[ライフゲーム]]は、値として 0 と 1 をとる外部総和型のセル・オートマトンの例である。同じく外部総和型でムーア近傍だが、規則をライフゲームとは変えたセル・オートマトンを欧米では "life-like" と呼ぶ<ref>"life-like cellular automaton" という用語の初出は少なくとも {{Harvtxt|Barral|Chaté|Manneville|1992}} まで遡るが、この文献では外部総和型全般をそのように呼んでおり、2次元に限定していない。</ref><ref>{{Cite book |title=Game of Life Cellular Automata |editor-first=Andrew |editor-last=Adamatzky |publisher=Springer |year=2010 |isbn=978-1-84996-216-2 |ref=harv}} - こちらはより限定的な意味で "life-like" と呼んでいる。</ref>。

=== その他 ===
CAの概念は様々な拡張が可能である。

[[ファイル:Oscillator.gif|right|frame|六角形のセルに基づくセル・オートマトン（ルール34/2）]]
例えば、矩形の格子ではなく別の多角形を使うという拡張がある。例えば[[六角形]]を平面に敷き詰めたとき、個々の六角形をセルとして扱うことができる。多くの場合そのようなセル・オートマトンは、矩形格子で近傍と規則をうまく調整したものと等価である。他にも[[ペンローズ・タイル]]のような[[平面充填]]で格子を形成することもできる<ref>http://www.newscientist.com/article/dn22134-first-gliders-navigate-everchanging-penrose-universe.html</ref>。

また、規則を決定的なものではなく確率的なものにする拡張もある。そのようなCAを{{仮リンク|確率的セル・オートマトン|en|probabilistic cellular automata}}と呼ぶ。この場合、時刻 ''t'' のパターンから時刻 ''t''+1 のとりうる各パターンの遷移確率が確率的規則により指定される。もっと単純な規則を使うこともあり、例えば「基本的にライフゲームの規則に従うが、毎回0.001%の確率で本来とは反対の色になる」といった規則を設定する。

時間や場所によって近傍の定義や規則を変化させるという拡張もある。例えば、最初の世代では水平方向の隣接したセルを近傍とするが、次の世代では垂直方向の隣接するセルを近傍とする、といった具合である。

CAでは、あるセルの新たな状態は、他のセルの新たな状態に影響されない。この原則を変更することもできる。

{{仮リンク|連続値セルオートマトン|en|continuous automaton}}と呼ばれるものもある。総和型と似ているが、規則や状態が離散値ではなく連続な値（一般に[[単位区間]]の値）を用いる。つまり、セルの状態は有限個の[[実数]]で表される。例えば、液体における拡散パターンのモデルなどに使われる。

[[:en:Continuous spatial automata|Continuous spatial automata]] では位置が連続的である。ある位置の状態は有限個の実数である。時間も連続的に推移し、状態は微分方程式にしたがって変化する。重要な例として[[反応拡散系]]があり、[[アラン・チューリング]]は[[シマウマ]]の縞模様やヒョウのドット模様を生み出した化学反応を説明する微分方程式を提案した<ref>{{Cite journal| last = Murray | first = J.|title = Mathematical Biology II |publisher = [[シュプリンガー・サイエンス・アンド・ビジネス・メディア|Springer]] }}</ref>。そのようなパターンをCAで近似的に生成することも可能である。continuous spatial automata でライフゲームのグライダーのような現象が生じる例も知られている<ref>Pivato, M: "RealLife: The continuum limit of Larger than Life cellular automata",  ''Theoretical Computer Science'', 372 (1), March 2007, pp.46-68</ref>。

== 1次元セル・オートマトン ==
最も単純だが自明ではないCAは、1次元で各セルは2つの状態をとることができ、近傍は両側に接している隣のセルという場合である。あるセルとその両側の3つのセルで近傍を構成するので、1つの近傍がとりうるパターンは 2<sup>3</sup>=8 種類となる。規則はそれらパターンについて、そのセルが次世代に1と0のどちら状態となるかを決定する。したがって規則群の組合せは 2<sup>8</sup>=256 通り存在する<ref name=bialynick-9/>。それら256種類のCAは一般にウルフラムが考案した0から255までのルール番号で参照され、これを{{仮リンク|ウルフラム・コード|en|Wolfram code}}と呼ぶ。これら256種類のCAはいくつかの論文で研究・比較されている。{{仮リンク|ルール30|en|rule 30}}と{{仮リンク|ルール110|en|rule 110}}のCAは特に興味深い。下図は、1カ所だけ1にした初期状態からのそれらCAの変化の様子を示している。図の各行がCAの1世代の履歴であり、一番上の行が ''t'' =0 である。各ピクセルは、0を白、1を黒で描画している。

===ルール30セル・オートマトン===
[[ファイル:CA rule30s.png|thumb]]
{|class=wikitable
!現在の状態!!中央のセルの次の状態
|-
|<table class=wikitable style="margin:0pt"><tr><td>0<td>0<td>0</table>
|<table class=wikitable style="margin:0pt"><tr><td>{{0|*}}<td>0<td>{{0|*}}</table>
|-
|<table class=wikitable style="margin:0pt"><tr><td>0<td>0<td>1</table>
|<table class=wikitable style="margin:0pt"><tr><td>{{0|*}}<td>1<td>{{0|*}}</table>
|-
|<table class=wikitable style="margin:0pt"><tr><td>0<td>1<td>0</table>
|<table class=wikitable style="margin:0pt"><tr><td>{{0|*}}<td>1<td>{{0|*}}</table>
|-
|<table class=wikitable style="margin:0pt"><tr><td>0<td>1<td>1</table>
|<table class=wikitable style="margin:0pt"><tr><td>{{0|*}}<td>1<td>{{0|*}}</table>
|-
|<table class=wikitable style="margin:0pt"><tr><td>1<td>0<td>0</table>
|<table class=wikitable style="margin:0pt"><tr><td>{{0|*}}<td>1<td>{{0|*}}</table>
|-
|<table class=wikitable style="margin:0pt"><tr><td>1<td>0<td>1</table>
|<table class=wikitable style="margin:0pt"><tr><td>{{0|*}}<td>0<td>{{0|*}}</table>
|-
|<table class=wikitable style="margin:0pt"><tr><td>1<td>1<td>0</table>
|<table class=wikitable style="margin:0pt"><tr><td>{{0|*}}<td>0<td>{{0|*}}</table>
|-
|<table class=wikitable style="margin:0pt"><tr><td>1<td>1<td>1</table>
|<table class=wikitable style="margin:0pt"><tr><td>{{0|*}}<td>0<td>{{0|*}}</table>
|}

===ルール110セル・オートマトン===
[[ファイル:CA rule110s.png|thumb]]
{|class=wikitable
!現在の状態!!中央のセルの次の状態
|-
|<table class=wikitable style="margin:0pt"><tr><td>0<td>0<td>0</table>
|<table class=wikitable style="margin:0pt"><tr><td>{{0|*}}<td>0<td>{{0|*}}</table>
|-
|<table class=wikitable style="margin:0pt"><tr><td>0<td>0<td>1</table>
|<table class=wikitable style="margin:0pt"><tr><td>{{0|*}}<td>1<td>{{0|*}}</table>
|-
|<table class=wikitable style="margin:0pt"><tr><td>0<td>1<td>0</table>
|<table class=wikitable style="margin:0pt"><tr><td>{{0|*}}<td>1<td>{{0|*}}</table>
|-
|<table class=wikitable style="margin:0pt"><tr><td>0<td>1<td>1</table>
|<table class=wikitable style="margin:0pt"><tr><td>{{0|*}}<td>1<td>{{0|*}}</table>
|-
|<table class=wikitable style="margin:0pt"><tr><td>1<td>0<td>0</table>
|<table class=wikitable style="margin:0pt"><tr><td>{{0|*}}<td>0<td>{{0|*}}</table>
|-
|<table class=wikitable style="margin:0pt"><tr><td>1<td>0<td>1</table>
|<table class=wikitable style="margin:0pt"><tr><td>{{0|*}}<td>1<td>{{0|*}}</table>
|-
|<table class=wikitable style="margin:0pt"><tr><td>1<td>1<td>0</table>
|<table class=wikitable style="margin:0pt"><tr><td>{{0|*}}<td>1<td>{{0|*}}</table>
|-
|<table class=wikitable style="margin:0pt"><tr><td>1<td>1<td>1</table>
|<table class=wikitable style="margin:0pt"><tr><td>{{0|*}}<td>0<td>{{0|*}}</table>
|}

例えば「ルール30」と呼ばれるのは、上の表のように時刻t+1における中央のセルの内部状態一覧を並べると0,0,0,1,1,1,1,0となっており、この[[二進記数法|2進数]]の数を[[十進記数法|10進数]]に直すと30であるためであり、これを{{仮リンク|ウルフラム・コード|en|Wolfram code}}と呼ぶ。

ルール30は「クラス3」の挙動を示し、単純な初期状態からもカオス的な経過を示し、無作為な履歴になっている。

ルール110はライフゲームのように「クラス4」の挙動を示し、完全な無作為でもなく、完全な反復でもない。局所的構造が現れ、様々な複雑な形で相互作用する。1994年ウルフラムの研究助手だったマシュー・クックは、それら構造の一部が[[チューリング完全]]性をサポートするのに十分であることを証明した。ルール110は非常に単純な1次元のシステムであり、具体的なことを実行するよう設計するのは困難であるため、この成果は興味深い。この結果からウルフラムはクラス4のセル・オートマトンが本質的にチューリング完全である可能性を示唆した。1998年、セル・オートマトンの学会が[[サンタフェ研究所]]で開催され、クックはその成果を発表したが、ウルフラムは {{lang|en|A New Kind of Science}} の出版前にその証明の詳細を公表したくなかったため、証明の詳細は発表されなかった<ref name=giles>{{Cite journal| author=Giles, Jim | title=What Kind of Science is This? | work=[[ネイチャー]] | issue=417 | pages=216–218 | year=2002}}</ref>。2004年、Cookの証明がウルフラムの発行する雑誌 ''[[:en:Complex Systems (journal)|Complex Systems]]'' (Vol. 15, No. 1) で発表された。実に証明してから10年が経過している。ルール110をベースとして極小の万能チューリングマシンが構築されている<ref>{{Cite journal| url= http://www.nybooks.com/articles/archives/2002/oct/24/is-the-universe-a-computer/?pagination=false | author=Weinberg, Steven | title=Is the Universe a Computer? | work=The New York Review of Books | publisher=Rea S. Hederman | date=October 24, 2002 | accessdate=October 12, 2012}}</ref>。

===ルール90===
また、ルール90の1次元セル・オートマトンは典型的な[[フラクタル]]図形である[[シェルピンスキーのギャスケット]]を生成する。（{{lang|en|[[WolframAlpha]]}}でルール90を見る→[http://www.wolframalpha.com/input/?i=rule+90 rule 90]）

[[File:SierpinskiTriangle.PNG|250px|シェルピンスキーのギャスケット|thumb]]
{|class=wikitable
!現在の状態!!中央のセルの次の状態
|-
|<table class=wikitable style="margin:0pt"><tr><td>0<td>0<td>0</table>
|<table class=wikitable style="margin:0pt"><tr><td>{{0|*}}<td>0<td>{{0|*}}</table>
|-
|<table class=wikitable style="margin:0pt"><tr><td>0<td>0<td>1</table>
|<table class=wikitable style="margin:0pt"><tr><td>{{0|*}}<td>1<td>{{0|*}}</table>
|-
|<table class=wikitable style="margin:0pt"><tr><td>0<td>1<td>0</table>
|<table class=wikitable style="margin:0pt"><tr><td>{{0|*}}<td>0<td>{{0|*}}</table>
|-
|<table class=wikitable style="margin:0pt"><tr><td>0<td>1<td>1</table>
|<table class=wikitable style="margin:0pt"><tr><td>{{0|*}}<td>1<td>{{0|*}}</table>
|-
|<table class=wikitable style="margin:0pt"><tr><td>1<td>0<td>0</table>
|<table class=wikitable style="margin:0pt"><tr><td>{{0|*}}<td>1<td>{{0|*}}</table>
|-
|<table class=wikitable style="margin:0pt"><tr><td>1<td>0<td>1</table>
|<table class=wikitable style="margin:0pt"><tr><td>{{0|*}}<td>0<td>{{0|*}}</table>
|-
|<table class=wikitable style="margin:0pt"><tr><td>1<td>1<td>0</table>
|<table class=wikitable style="margin:0pt"><tr><td>{{0|*}}<td>1<td>{{0|*}}</table>
|-
|<table class=wikitable style="margin:0pt"><tr><td>1<td>1<td>1</table>
|<table class=wikitable style="margin:0pt"><tr><td>{{0|*}}<td>0<td>{{0|*}}</table>
|}

== 生物学における例 ==
[[File:Textile cone.JPG|thumb|right|240px|[[イモガイ]]の一種タガヤサンミナシのセル・オートマトン状模様の貝殻<ref name=coombs/>]]
一部の生物学的過程はセル・オートマトンでシミュレートできる。

[[イモガイ]]やガクフボラといった貝の[[貝殻]]の模様はセル・オートマトンの描くパターンによく似ている。貝殻の辺縁に狭い帯状に色素細胞がある。各色素細胞は活性化されると色素を[[分泌]]し、同時に近傍の色素細胞の活性化を阻害するようになっており、天然のセル・オートマトンの規則のように作用する<ref name=coombs>{{Citation| url= http://www.maths.nott.ac.uk/personal/sc/pdfs/Seashells09.pdf | author=Coombs, Stephen |title=The Geometry and Pigmentation of Seashells | pages=3–4 | date=February 15, 2009 | accessdate=2012-09-02}}</ref>。この色素細胞の帯が貝殻に色の模様を残しつつ、少しずつ貝殻が成長していく。例えば、イモガイの一種タガヤサンミナシはウルフラムが研究した{{仮リンク|ルール30|en|rule 30}}CAとよく似た模様である<ref name=coombs/>。

植物はCA的機構で気体の吸入と排出を行っている。葉に多数存在する[[気孔]]がセル・オートマトンのセルのように振る舞う<ref>{{Cite journal| doi = 10.1073/pnas.0307811100 | last1 = Peak | first1 = West | last2 = Messinger | first2 = Mott | year = 2004 | title = Evidence for complex, collective dynamics and emergent, distributed computation in plants | url = http://www.pnas.org/cgi/content/abstract/101/4/918 | journal = Proceedings of the National Institute of Science of the USA | volume = 101 | issue = 4| pages = 918–922 |bibcode = 2004PNAS..101..918P | ref = harv | pmid=14732685 | pmc=327117}}</ref>。

[[頭足類]]は表皮に[[色素胞]]があり、体表の模様を変化させるが、これを2状態で2次元のセル・オートマトンでシミュレートできる。各状態は色素胞を広げた状態と縮めた状態に対応する<ref>http://gilly.stanford.edu/past_research_files/APackardneuralnet.pdf</ref>。

[[神経細胞]]をシミュレートするしきい値型CAが考案されており、認知や学習といった複雑な挙動をシミュレートできる。

[[線維芽細胞]]もセル・オートマトンと似た挙動を示す。個々の線維芽細胞はその近傍の細胞としか相互作用しない<ref>{{Cite book|title=Disordered Systems and Biological Organization|year=1986|pages=374–375|author=Yves Bouligand}}</ref>。

== 化学における例 ==
[[ベロウソフ・ジャボチンスキー反応]]はセル・オートマトンを使ってシミュレートできる。1950年代、A・M・ジャボチンスキーは[[ソビエト連邦|ソ連]]の{{仮リンク|B・P・ベロウソフ|en|Boris Pavlovich Belousov}}の研究成果をさらに進め、[[マロン酸]]、酸化した[[臭素酸]]塩、[[セリウム]][[塩]]の混合物の薄い均一な層を置いておくと、同心円や渦巻き模様などの幾何学的模様が生じることを発見した。1988年8月、[[サイエンティフィック・アメリカン]]（日本では[[日経サイエンス]]）誌上の "Computer Recreation" という記事で<ref>A. K. Dewdney, The hodgepodge machine makes waves, Scientific American, p. 104, August 1988.</ref>、A. K. Dewdney はベロウソフ・ジャボチンスキー反応に非常によく似た挙動を示すセル・オートマトンを紹介した<ref>M. Gerhardt and H. Schuster, A cellular automaton describing the formation of spatially ordered structures in chemical systems, Physica D 36, 209-221, 1989.</ref>。ベロウソフ・ジャボチンスキー反応が、分子レベルでそのセル・オートマトンと同じような仕組みで発生しているのかどうかは不明である。これまで、セル・オートマトン的な化学反応が自然界で観察されたことはない。そのような化学反応は全て研究室や実験室でのみ観測されている。

== 物理における例 ==
[[ソリトン]]のようなふるまいを見せる、箱玉系と呼ばれているセル・オートマトンがある。

== 応用 ==
=== 並列コンピュータ ===
離散的(非連続的)時間で記述され、時刻t+1における1つのセルの内部状態は、時刻tにおける状態によって決定されるといった点で、セル・オートマトンは[[チューリングマシン]]とよく似ている。実際、万能チューリングマシンと等価な動作をするセル・オートマトンが存在することが知られている。しかし、チューリングマシンは「逐次的な処理を行うデジタル[[コンピュータ]]」のモデルであるのに対し、セル・オートマトンは各セルが並列に演算処理を実現しており、いわば "並列コンピュータ" であるという点で大きく異なる。

セル・オートマトンの概念をハードウェアで実装して情報処理を行おうとする試みも行われている。処理要素は格子状に配置され、2次元か3次元の[[平面充填]]構造とされる。それ以外の並べ方も可能だが、まだ試されたことはない。各処理要素（すなわちセル）は隣接する少数のセルだけとやり取りする。遠いセルとの直接通信手段は存在しない。セルの相互作用には、電荷、磁化、振動などの物理的な手段を使う。いずれにしても各処理要素間を結線する必要はない。これは、今日の[[ノイマン型]]コンピュータのプロセッサとはかなり違う。

例えば{{仮リンク|シストリックアレイ|en|systolic array}}はCAプロセッサアレイの一例である。

==== 遺伝的アルゴリズムを使った進化するセル・オートマトン ====
[[センサーネットワーク]]やさらに微細な構造をネットワークとして設計し、分散処理を行わせることに関心が集まっている。[[分散コンピューティング|分散システム]]を使い大域的なレベルで情報処理するという考え方から[[創発]]計算というアイデアが生まれた<ref name="autogenerated1">The Evolution of Emergent Computation, James P. Crutchfield and Melanie Mitchell (SFI Technical Report 94-03-012)</ref>。[[ポートランド州立大学]]の教授で[[サンタフェ研究所]]にも所属している{{仮リンク|メラニー・ミッチェル|en|Melanie Mitchell}}<ref>http://www.santafe.edu/about/people/profile/Melanie%20Mitchell</ref>は、そのために自己進化するセルの格子を使うアイデアに取り組んでいる<ref name="autogenerated1"/>。ミッチェルらはセル格子のプログラムに[[進化的アルゴリズム]]を採用している<ref name="autogenerated3">The Evolutionary Design of Collective Computation in Cellular Automata, James P. Crutchfeld, Melanie Mitchell, Rajarshi Das (In J. P. Crutch¯eld and P. K. Schuster (editors), Evolutionary Dynamics|Exploring the Interplay of Selection, Neutrality, Accident, and Function. New York: Oxford University Press, 2002.)</ref>。分散型システムにおける計算は古典的なコンピュータとは大きく異なり、大域的および局所的なパターンの変化という形で情報処理がなされる。

この手法の発想の元になっているのは、[[社会性昆虫]]、[[神経系]]、経済システムといった自然界に見られる複雑なシステムである<ref name="autogenerated3" />。研究の焦点は、進化する分散型システムでいかにして計算が発生するかを解明することである。モデルを構築しどのようにして創発計算が生じるかを解明するため、ミッチェルらはセル・オートマトン内のパターンを進化させるべく[[遺伝的アルゴリズム]] (GA) を適用した。既にGAによって洗練された創発計算戦略が生じる規則を発見している<ref name="autogenerated2">Evolving Cellular Automata with Genetic Algorithms: A Review of Recent Work, Melanie Mitchell, James P. Crutchfeld, Rajarshi Das (In Proceedings of the First International Conference on Evolutionary Computation and Its Applications (EvCA'96). Moscow, Russia: Russian Academy of Sciences, 1996.)</ref>。ミッチェルらが採用したのは1次元2値で6個の近傍を持つセル・オートマトンである。先頭と末尾は繋がっているので、環状になっている。

=== 暗号 ===
ルール30は、[[ブロック暗号]]に応用可能ではないかと言われていた。2次元セル・オートマトンを乱数発生に使った例がある<ref>{{Cite journal| first1=M. | last1=Tomassini | first2=M. | last2=Sipper | first3=M. | last3=Perrenoud | title=On the generation of high-quality random numbers by two-dimensional cellular automata | work=IEEE Transactions on Computers | volume=49 | issue=10 | pages=1146–1151 | year=2000}}</ref>。

セル・オートマトンを[[公開鍵暗号]]に使うことも提案されてきた。有限なセル・オートマトンの変化は[[一方向性関数]]と考えられ、その逆関数を見つけることは困難と考えられているためである。ルールを与えられると、誰でも簡単に次の状態を計算することはできるが、現在状態から以前の状態を求めることは非常に難しい。しかし、ルール設計者は容易に逆関数を求める方法を作ることができる。従って、これは一種の[[落とし戸関数]]であり、公開鍵暗号に活用できる。このような原理に基づいたセキュリティシステムは今のところ知られていない。

=== 誤り訂正符号 ===
セル・オートマトンを[[誤り検出訂正|誤り訂正符号]]の設計に応用した例として、D. Roy Chowdhury、S. Basu、I. Sen Gupta、P. Pal Chaudhuri の論文 "Design of CAECC - Cellular Automata Based Error Correcting Code" がある。この論文ではセル・オートマトンを使って SEC-DED符号（1ビット誤り訂正-2ビット誤り検出符号）を構築する新たな手法が定義されており、その符号の高速ハードウェアデコーダも報告されている。

== 物質世界の基盤のモデルとしてのCA ==
{{Main|デジタル物理学}}
Andrew Ilachinski は著書 ''Cellular Automata'' で、多くの学者が宇宙自体がセル・オートマトンなのではないかという疑問を投げかけていると指摘した<ref name=ilachinski-660>{{Harvnb|Ilachinski|2001|p=660}}</ref>。Ilachinskiは、この問題の重要性を示すには簡単な観察をしてみるのがよいと主張し、例えば{{仮リンク|ルール110|en|rule 110}}の発展するパターンをどうやったらうまく説明できるか考えてみるのがよいとした<ref name=ilachinski-661-662>{{Harvnb|Ilachinski|2001|pp=661–662}}</ref>。そして、もしそのイメージの生成方法を知らないとしたら、何らかの粒子状のオブジェクトの運動の軌跡ではないかと推測するだろうと述べている。実際、物理学者 [[:en:James P. Crutchfield|James Crutchfield]] はその考え方から厳密な数学的理論を構築した<ref>J. P. Crutchfield, [http://csc.ucdavis.edu/~cmg/papers/CalcEmerg.pdf <nowiki>"The Calculi of Emergence: Computation, Dynamics, and Induction"</nowiki>], Physica D 75, 11-54, 1994.</ref>。この考え方を推し進めていくと、[[素粒子物理学]]で説明されている我々の世界も根底ではCAと見なせるのではないかという考え方に到達する。

その考え方に沿った理論はまだ発展途中だが、この仮説に興味を惹かれた学者らが離散的フレームワークで世界を理解することについて興味深い憶測と有益な直観を示している。[[人工知能|AI]]研究者[[マービン・ミンスキー]]は、4次元CA格子で素粒子の相互作用を理解する方法を研究した<ref>M. Minsky, "Cellular Vacuum", International Journal of Theoretical Physics 21, 537-551, 1982.</ref>。コンピュータの先駆者[[コンラート・ツーゼ]]は、素粒子の持つ情報についての問題を解くため、不規則な格子を考案した<ref>K. Zuse, "The Computing Universe", Int. Jour. of Theo. Phy. 21, 589-600, 1982.</ref>。また[[エドワード・フレドキン]]は "finite nature hypothesis" と名付けた仮説を提唱。「最終的に時間や空間を含む全ての物理量は離散的で有限だと判明するだろう」とした<ref>E. Fredkin, "Digital mechanics: an informational process based on reversible universal cellular automata", Physica D 45, 254-270, 1990</ref>。フレドキンとウルフラムは[[デジタル物理学]]の信奉者である。

21世紀に入ると、非標準計算についての著作からこの考え方に沿った示唆が生まれている。ウルフラムの ''[[:en:A New Kind of Science|A New Kind of Science]]'' では、CAが物理学を含めた様々な主題を理解する鍵だとしている。（Francesco Berto が創始し、Gabriele Rossi と Jacopo Tagliabue が発展させた）[[:en:iLabs|iLabs]]<ref>[http://www.ilabs.it/ iLabs]</ref>が2010年に出版した ''Mathematics Of the Models of Reference'' では「菱形十二面体」をベースとする格子と独特の規則で2次元および3次元の宇宙を説明するモデルを提案している。このモデルは[[チューリングマシン]]と等価であり、完全な可逆性を有し（様々な量を保存し、情報を決して失わない）、宇宙の発展についての質的な論述を計算できる論理が組み込まれている<ref>[http://www.mmdr.it/defaultEN.asp F. Berto, G. Rossi, J. Tagliabue, The Mathematics of the Models of Reference], College Publications, 2010</ref>。

== ポップカルチャーにおけるセル・オートマトン ==
* 『[[NUMBERS 天才数学者の事件ファイル]]』シーズン2のエピソード「誘拐事件の真相」にて、1次元セルオートマトンへの言及がある<ref>{{Cite web |last=Weisstein |first=Eric W. |title=Cellular Automaton |url= http://mathworld.wolfram.com/CellularAutomaton.html |accessdate=2011-03-13}}</ref>。
* [[エリック・レイモンド]]は[[ハッカー文化]]のシンボルとして、[[ライフゲーム]]の[[グライダー (ライフゲーム)|グライダー]]を描いたエンブレムを提案した<ref>[http://www.catb.org/hacker-emblem/ the Hacker Emblem page on Eric S. Raymond's site]</ref>。
* [[グレッグ・イーガン]]の小説『順列都市』（早川文庫）では、オートヴァースと呼ばれる[[人工生命]]シミュレータが登場する<ref>{{Cite book |contribution=Greg Egan |pages=190–200 |title=Strange constellations: a history of Australian science fiction |volume=80 |series=Contributions to the study of science fiction and fantasy |first1=Russell |last1=Blackford |first2=Van |last2=Ikin |first3=Sean |last3=McMullen |publisher=Greenwood Publishing Group |year=1999 |isbn=978-0-313-25112-2 |ref=harv}}</ref><ref>{{Cite book |contribution=Subjective cosmology and the regime of computation: intermediation in Greg Egan's fiction |pages=214–240 |title=My mother was a computer: digital subjects and literary texts |first=N. Katherine |last=Hayles |publisher=University of Chicago Press |year=2005 |isbn=978-0-226-32147-9 |ref=harv}}</ref>。
* [[ウィル・マッカーシイ]]の小説 ''[[:en:Bloom (novel)|Bloom]]'' では、セル・オートマトンを論じている<ref>{{Cite web |last=Kasman |first=Alex |title=MathFiction: Bloom |url= http://kasmana.people.cofc.edu/MATHFICT/mfview.php?callnumber=mf615| accessdate=2011-03-27}}</ref>。
* [[ロバート・J・ソウヤー]]の ''[[:en:Wake (Robert J. Sawyer novel)|WWW]]'' 三部作ではセル・オートマトンが重要な役割を演じ、ウェブ上の人工生命が意識を獲得する方法に関係している<ref>http://www.sfwriter.com/syw1.htm</ref>。

== 具体例 ==
* [[コッドのセル・オートマトン]]
* [[ライフゲーム]]
* [[ラングトンのループ]]
* [[ラングトンのアリ]]
* [[ワイヤワールド]]
* [[非同期セル・オートマトン]]

== 脚注 ==
{{Reflist|2}}

== 参考文献 ==
{{Refbegin|2}}
* 『アインシュタインの部屋』上・下 - エド・レジス著／大貫昌子訳　工作舎　ISBN 978-4-87502-171-1・ISBN 978-4-87502-172-8
* 『コンピューターレクリエーションI 遊びの発想』 - A.K.デュードニー著 別冊サイエンス32
* 『哲学者クロサキと工学者アイハラの神はカオスに宿りたもう』 - 合原 一幸、 黒崎 政男 共著
* 『箱玉系の数理』 - 時弘哲治 朝倉書店
*{{Cite book| first1=Iwo | last1=Bialynicki-Birula | first2=Iwona | last2=Bialynicka-Birula | title=Modeling Reality: How Computers Mirror Life | year=2004 | publisher=[[オックスフォード大学出版局|Oxford University Press]] | isbn=0198531001| ref=harv}}
*{{Cite book| first1=Bastien | last1=Chopard | first2=Michel | last2=Droz | title=Cellular Automata Modeling of Physical Systems | year=2005 | publisher=[[ケンブリッジ大学出版局|Cambridge University Press]] | isbn=0-521-46168-5 | ref=harv}}
*{{Cite book| editor=Gutowitz, Howard | title=Cellular Automata: Theory and Experiment | year=1991 | publisher=[[マサチューセッツ工科大学出版局|MIT Press]] | isbn=9780262570862 | ref={{SfnRef|Kari, Jarrko|1991}}}}
*{{Cite book| last=Ilachinski |first=Andrew | title=Cellular Automata: A Discrete Universe | year=2001 | publisher=World Scientific | isbn=9789812381835 | ref=harv}}
*{{Cite book| first1=Lemont B. | last1=Kier | first2=Paul G. | last2=Seybold | first3=Chao-Kun | last3=Cheng | title=Modeling Chemical Systems using Cellular Automata | year=2005 | publisher=Springer | isbn=9781402036576 | ref=harv}}
*{{Cite book| last=Schiff |first=Joel L. | title=Cellular Automata: A Discrete View of the World | year=2011 | publisher=Wiley & Sons, Inc | isbn=9781118030639 | ref=harv}}
*{{Cite book| last=Wolfram |first=Stephen | authorlink=スティーブン・ウルフラム | title=A New Kind of Science | year=2002 | publisher=[[ウルフラム・リサーチ|Wolfram Media]] | isbn=978-1579550080 | ref=harv}}
*{{Cite journal |title=Collective behaviors in a family of high-dimensional cellular automata |first1=Bernard |last1=Barral |first2=Hugues |last2=Chaté |first3=Paul |last3=Manneville |journal=Physics Letters A |volume=163 |issue=4 |year=1992 |pages=279–285 |doi=10.1016/0375-9601(92)91013-H |ref=harv}}
*[http://cafaq.com/ Cellular automaton FAQ] from the newsgroup comp.theory.cell-automata
*A. D. Wissner-Gross. 2007. ''[http://www.alexwg.org/publications/JCellAuto_4-27.pdf Pattern formation without favored local interactions]'', Journal of Cellular Automata 4, 27-36 (2008).
*[http://cell-auto.com/neighbourhood/index.html "Neighbourhood Survey"] 三角格子や大きな近傍のセル・オートマトンなどを論じている
* von Neumann, John, 1966, ''The Theory of Self-reproducing Automata'', A. Burks, ed., Univ. of Illinois Press, Urbana, IL.
**『自己増殖オートマトンの理論』- フォン・ノイマン著 岩波書店
*[http://cscs.umich.edu/~crshalizi/notebooks/cellular-automata.html Cosma Shalizi's Cellular Automata Notebook] 書誌情報が豊富
*[http://www.stephenwolfram.com/publications/articles/ca/ Wolfram's papers on CAs]
**[http://www.wolframscience.com/reference/notes/876b "History of Cellular Automata"] from [[スティーブン・ウルフラム|Stephen Wolfram]]'s ''A New Kind of Science'' 
** Wolfram, Stephen, 1985, ''[http://www.stephenwolfram.com/publications/articles/ca/85-cryptography/1/text.html Cryptography with Cellular Automata]'', CRYPTO'85. 
* A.M. Turing. 1952. The Chemical Basis of Morphogenesis. ''Phil. Trans. Royal Society'', vol. B237, pp.&nbsp;37 – 72. - 連続的オートマトンの一種を提唱している。
* Evolving Cellular Automata with Genetic Algorithms: A Review of Recent Work, Melanie Mitchell, James P. Crutchfeld, Rajarshi Das (In Proceedings of the First International Conference on Evolutionary Computation and Its Applications (EvCA'96). Moscow, Russia: Russian Academy of Sciences, 1996.)
* The Evolutionary Design of Collective Computation in Cellular Automata, James P. Crutchfeld, Melanie Mitchell, Rajarshi Das (In J. P. Crutch¯eld and P. K. Schuster (editors), Evolutionary Dynamics|Exploring the Interplay of Selection, Neutrality, Accident, and Function. New York: Oxford University Press, 2002.)
*The Evolution of Emergent Computation, James P. Crutchfield and Melanie Mitchell (SFI Technical Report 94-03-012)
*[http://www.wepapers.com/Papers/16352/files/swf/15001To20000/16352.swf Ganguly, Sikdar, Deutsch and Chaudhuri "A Survey on Cellular Automata"]
*[http://www.idsia.ch/~juergen/digitalphysics.html Zuse´s publications on CA-based physics (1967, 1969, 1970)], with comments by Juergen Schmidhuber
* Klaus  Sutner. 1989. ''A  Note on Culik-Yu Classes'' Complex Systems  3 (1989) 107-115.
{{Refend}}

== 関連項目 ==
* [[オートマトン]]
* [[クリストファー・ラングトン|λパラメータ]]
* [[パーコレーション]]
* [[格子ボルツマン法]]
* [[格子気体法]]
* [[光速 (セル・オートマトン)]]
* [[ドゥッチ数列]]

== 外部リンク ==
{{Commonscat|Cellular automata}}
*[http://www.mirekw.com/ca/ Mirek's Cellebration] - フリーなセル・オートマトン探索ソフトウェア MCell（Windows）と MJCell（Javaアプレット）のホームページ。1次元と2次元の各種セル・オートマトンをサポートしたソフトウェア。ルールとイメージも豊富にある。ソースコードもある。
*[http://www.collidoscope.com/modernca/ Modern Cellular Automata] - 各種2次元セル・オートマトンが見られる（Javaアプレット）。
*[http://necsi.org/postdocs/sayama/sdsr/java/ Self-replication loops in Cellular Space] - 自己複製ループのJavaアプレット
*[http://vlab.infotech.monash.edu.au/simulations/cellular-automata/ Cellular Automata] - セル・オートマトンのアプレット群がある (Monash University's Virtual Lab)
*[http://www.sourceforge.net/projects/golly Golly] ライフゲームをはじめとする各種セル・オートマトンのシミュレータ。フォン・ノイマンのセル・オートマトンもシミュレートできる。
*[http://atlas.wolfram.com/TOC/TOC_200.html Wolfram Atlas] – 各種1次元セル・オートマトンの一覧
*[http://www.conwaylife.com/ Conway Life]
*[http://www.newscientist.com/article/mg20627653.800-first-replicating-creature-spawned-in-life-simulator.html First replicating creature spawned in life simulator]
*[http://www.mmdr.it/provaEN.asp ''The Mathematics of the Models of Reference'']
*[http://www.fourmilab.ch/cellab Fourmilab Cellular Automata Laboratory]
*[http://busyboxes.org Busy Boxes], a 3-D, reversible, [http://64.78.31.152/wp-content/uploads/2012/08/2stateRevCAin3D.pdf SALT]-architecture CA
*{{SEP|cellular-automata|Cellular Automata}}

{{Good article}}

{{DEFAULTSORT:せるおおとまとん}}
[[Category:セル・オートマトン|*]]
[[Category:数学に関する記事]]

{{Link GA|es}}