セルオートマトン

セルオートマトン（複数形：セルラーオートマトン、略称：CA ）は、オートマトン理論で研究される離散計算モデルです。セルラーオートマトンには、セル空間、テッセレーションオートマトン、均質構造、セルラー構造、テッセレーション構造、反復配列などと呼ばれることもあります。^{[2]セルラーオートマトンは、}物理学、理論生物学、微細構造モデリング など、さまざまな分野で応用されています。

セルオートマトンとは、セルの規則的なグリッドで構成され、各セルはオンやオフなど、有限の数の状態のいずれかになります（結合マップ格子とは対照的です）。グリッドは、任意の有限数の次元にすることができます。各セルについて、指定されたセルを基準として、近傍と呼ばれるセルのセットが定義されます。初期状態（時間t = 0）は、各セルに状態 を割り当てることによって選択されます。新しい世代は、セルの現在の状態と近傍のセルの状態に基づいて各セルの新しい状態を決定する一定のルール（通常は数学関数）^[3]に従って作成されます（tを1進めます）。通常、セルの状態を更新するためのルールは各セルに対して同じで、時間の経過とともに変化せず、グリッド全体に同時に適用されますが、^[4]確率的セルオートマトンや非同期セルオートマトンなどの例外が知られています。

この概念はもともと、1940年代にロスアラモス国立研究所で同期だったスタニスワフ・ウラムとジョン・フォン・ノイマンによって発見されました。1950年代から1960年代にかけて研究されていましたが、1970年代にコンウェイのライフゲーム（2次元セルオートマトン）が登場して初めて、このテーマへの関心は学問の世界を超えて広がりました。1980年代には、スティーブン・ウルフラムが1次元セルオートマトン、または彼が基本セルオートマトンと呼ぶものの体系的な研究に取り組み、彼の研究助手マシュー・クックがこれらのルールの1つがチューリング完全であることを示しました。

ウルフラムが概説したセルオートマトンの主な分類は、1から4の番号が付けられている。順に、パターンが一般に均質に安定するオートマトン、パターンがほぼ安定または振動する構造に進化するオートマトン、パターンが一見無秩序な形で進化するオートマトン、パターンが極めて複雑になり、安定した局所構造を伴って長期間持続するオートマトンである。この最後のクラスは、計算上普遍的、つまりチューリングマシンをシミュレートできると考えられている。特殊なタイプのセルオートマトンには、単一の構成のみが次の構成に直接つながる可逆的なものや、個々のセルの将来の値が隣接するセルのグループの合計値のみに依存する全体主義的なものなどがある。セルオートマトンでは、生物学的システムや化学的システムを含むさまざまな現実世界のシステムをシミュレートできる。

2 次元セルオートマトンをシミュレートする方法の 1 つは、無限のグラフ用紙と、セルが従う一連のルールを使用することです。各正方形は「セル」と呼ばれ、各セルには黒と白の 2 つの状態があります。セルの近傍とは、近くの、通常は隣接するセルのことです。最も一般的な 2 つの近傍の種類は、フォン ノイマン近傍とムーア近傍です。^[5]前者は、セルオートマトン理論の創始者にちなんで名付けられ、4 つの直交する隣接するセルで構成されます。^[5]後者には、フォン ノイマン近傍と 4 つの対角線上の隣接するセルが含まれます。^{[5]このようなセルとそのムーア近傍には、512 (= 2 9} ) の可能なパターンがあります。512 の可能なパターンのそれぞれについて、ルール テーブルには、次の時間間隔で中央のセルが黒になるか白になるかが示されます。コンウェイのライフ ゲームは、このモデルの一般的なバージョンです。もう一つの一般的な近傍型は拡張フォン・ノイマン近傍で、これは各直交方向で最も近い2つのセルを含み、合計8つになります。^[5]オートマトンの総数の一般的な方程式はk ^{k s}で、kはセルの可能な状態の数、sはセルの次の状態を決定するために使用される隣接セルの数（計算されるセル自体を含む）です。^[6]したがって、ムーア近傍を持つ2次元システムでは、可能なオートマトンの総数は2 ^{2 9}、つまり1.34 × 10 ¹⁵⁴。

通常、宇宙のすべてのセルは、他の状態にある有限数のセルを除いて、同じ状態から始まると想定されます。状態値の割り当ては構成と呼ばれます。 [ ^7]より一般的には、宇宙は周期的なパターンで覆われた状態から始まり、有限数のセルのみがそのパターンを破ると想定されることがあります。後者の仮定は、1次元セルオートマトンでは一般的です。

セルオートマトンは通常、無限グリッドではなく有限グリッド上でシミュレートされます。2 次元では、宇宙は無限平面ではなく長方形になります。有限グリッドの明らかな問題は、端にあるセルをどのように処理するかです。それらの処理方法は、グリッド内のすべてのセルの値に影響します。考えられる方法の 1 つは、それらのセルの値を一定のままにすることです。もう 1 つの方法は、これらのセルの近傍を別の方法で定義することです。近傍の数が少ないと言うこともできますが、その場合、端にあるセルの新しいルールも定義する必要があります。これらのセルは通常、周期境界条件で処理され、その結果、トロイダル配置になります。つまり、上から外れると、下の対応する位置から 1 つが入り、左から外れると、右から 1 つが入ります。 (これは本質的には無限周期タイリングをシミュレートするもので、偏微分方程式の分野では周期境界条件と呼ばれることもあります。) これは、長方形の左端と右端をテープで留めてチューブを形成し、次にチューブの上端と下端をテープで留めてトーラス(ドーナツ形) を形成するものとして視覚化できます。他の次元の宇宙も同様に処理されます。これは近傍を使用して境界問題を解決しますが、もう 1 つの利点は、モジュラー算術関数を使用して簡単にプログラムできることです。たとえば、以下の例のような 1 次元セルオートマトンでは、セルx _i ^tの近傍は{ x _{i −1} ^{t −1}、x _i ^{t −1}、x _{i +1} ^{t −1} } です。ここで、 tは時間ステップ (垂直)、i は1 世代のインデックス (水平) です。

スタニスワフ・ウラムは、 1940年代にロスアラモス国立研究所で働いていたとき、単純な格子ネットワークをモデルにして結晶の成長を研究しました。^[8]同じ頃、ロスアラモスでのウラムの同僚であるジョン・フォン・ノイマンは、自己複製システムの問題に取り組んでいました。^[9]フォン・ノイマンの最初の設計は、1台のロボットが別のロボットを構築するという概念に基づいていました。この設計は運動学モデルとして知られています。^{[10] [11]}この設計を開発するにつれて、フォン・ノイマンは自己複製ロボットを構築することの大きな困難さと、そのレプリカントを構築するための「部品の海」をロボットに提供することの多大なコストを認識するようになりました。ノイマンは1948年のヒクソンシンポジウムで「オートマトンに関する一般論理理論」と題する論文を執筆した。^[9]ウラムは、自己複製の還元主義モデルを作成するために離散システムを使用することを提案した人物である。 ^{[12] [13]} ニルス・オール・バリチェリは、これらの人工生命モデルの初期の研究の多くを行った。

ウラムとフォン・ノイマンは1950年代後半に液体の運動を計算する方法を考案した。この方法の基本的な概念は、液体を個別の単位の集まりと見なし、各単位の運動をその近傍の挙動に基づいて計算するというものである。^[14]こうして最初のセルオートマトンシステムが誕生した。ウラムの格子ネットワークと同様に、フォン・ノイマンのセルオートマトンも2次元であり、自己複製子はアルゴリズム的に実装されている。その結果、小さな近傍（接触するセルのみが近傍であり、フォン・ノイマンのセルオートマトンの場合は直交セルのみ）とセルあたり29の状態を持つセルオートマトン内で動作する汎用コピー機およびコンストラクターが生まれた。^[15]フォン・ノイマンは、特定のパターンが与えられたセル宇宙内で自分自身を無限にコピーできることを、それが可能な20万セル構成を設計することで証明した。^[15]この設計はテッセレーションモデルとして知られており、フォン・ノイマンの万能構築子と呼ばれています。^[16]

1940年代には、ノーバート・ウィーナーとアルトゥーロ・ローゼンブルースも、セルオートマトンの特徴を持つ興奮性媒体のモデルを開発した。^[17]彼らの具体的な動機は、心臓系におけるインパルス伝導の数学的記述であった。しかし、信号が伝わる媒体は連続的で、波面は曲線であるため、彼らのモデルはセルオートマトンではない。^{[17] [18]興奮性媒体の真のセルオートマトンモデルは、1978年にJMグリーンバーグとSPヘイスティングスによって開発され、研究された。}グリーンバーグ-ヘイスティングスセルオートマトンを参照。ウィーナーとローゼンブルースのオリジナルの研究には多くの洞察が含まれており、心臓不整脈と興奮性システムに関する現代の研究出版物で引用され続けている。^[19]

1960年代に、セルオートマトンが特別なタイプの力学システムとして研究され、記号力学という数学の分野とのつながりが初めて確立されました。1969年に、Gustav A. Hedlundは、この観点に基づいた多くの結果を^[20]、セルオートマトンの数学的研究における独創的な論文と今でも考えられている論文にまとめました。最も基本的な結果は、Curtis-Hedlund-Lyndonの定理において、セルオートマトンの大域的規則の集合をシフト空間の連続 自己準同型の集合として特徴付けたことです。

1969年、ドイツのコンピュータの先駆者コンラート・ツーゼは著書『空間計算』を出版し、宇宙の物理法則は本質的に離散的であり、宇宙全体は単一のセルオートマトンによる決定論的計算の出力であると提唱した。「ツーゼの理論」はデジタル物理学と呼ばれる研究分野の基礎となった。^[21]

同じく 1969 年に、コンピュータ科学者のAlvy Ray Smith がセルオートマトン理論に関するスタンフォード大学の博士論文を完成させました。これは CA を一般的なコンピュータのクラスとして初めて数学的に扱ったものです。この論文からは多くの論文が生まれました。彼はさまざまな形状の近傍の同値性、ムーア近傍をフォン ノイマン近傍に縮小する方法、または任意の近傍をフォン ノイマン近傍に縮小する方法を示しました。^[22]彼は2 次元 CA が計算汎用性があることを証明し、1 次元 CA を導入して、単純な近傍であっても 1 次元 CA も計算汎​​用性があることを示しました。 ^[23]彼は、複雑なフォン ノイマンの証明 (つまり、自己複製マシンの構築汎用性) を 1 次元 CA における計算汎用性の帰結に組み込む方法を示しました。^[24]フォン・ノイマンのCAに関する本のドイツ語版の序文として書かれたもので、彼はこの分野の概説を執筆し、多くの国で多くの著者が10年以上かけて書いた、現代のCA研究者が見落としがちな論文を多数引用している。^[25]

1970年代には、2つの状態を持つ2次元セルオートマトン「ライフゲーム」が、特に初期のコンピューティングコミュニティで広く知られるようになりました。ジョン・コンウェイによって発明され、マーティン・ガードナーによってサイエンティフィック・アメリカン誌の記事^[26]で広められたこのゲームのルールは次のとおりです。

1. 生きているセルの近傍の生存セル数が 2 個未満の場合、そのセルは過密状態によって死滅します。
2. 2 つまたは 3 つの生きている隣接細胞を持つ生きている細胞は、次の世代に生き続けます。
3. 3 つ以上の生きている隣接セルを持つ生きているセルは、人口過剰によって死滅します。
4. ちょうど 3 つの生きている隣接細胞を持つ死んだ細胞は、再生したかのように生きた細胞になります。

その単純さにもかかわらず、このシステムは、見かけ上のランダム性と秩序性の間を変動しながら、驚くほど多様な動作を実現しています。ライフゲームの最も顕著な特徴の 1 つは、グライダーが頻繁に出現することです。グライダーとは、基本的にグリッド上を自ら移動するセルの配置です。グライダーが相互作用して計算を実行するようにオートマトンを配置することが可能であり、多大な努力の末、ライフゲームは汎用チューリングマシンをエミュレートできることが示されました。^[27]これは主に娯楽的なトピックと見なされ、1970 年代初頭にライフゲームの特殊性といくつかの関連ルールを調査した以外は、フォローアップ作業はほとんど行われませんでした。^[28]

スティーブン・ウルフラムは、自然界では複雑なパターンが熱力学の第二法則に反して形成されているように見えることに着目した後、1981年半ばに独自にセルオートマトンの研究を始めた。^{[29]彼の研究は当初、脳に見られる}神経ネットワークなどのシステムをモデル化したいという願望によって促進された。^[29]彼は1983年6月にReviews of Modern Physicsに基本的なセルオートマトン（特にルール30 ）を調査した最初の論文を発表した^{。[2] [29]}これらの単純なルールの動作の予想外の複雑さから、ウルフラムは自然界の複雑さも同様のメカニズムによるのではないかと考えるようになった。^[29]しかし、研究を進めるうちに、セルオートマトンではニューラルネットワークのモデル化が不十分であることが判明した。^[29]さらに、この時期にウルフラムは、本質的ランダム性と計算上の不可分性の概念を定式化し、^[30]ルール110が普遍的である可能性があることを示唆しました。この事実は、1990年代にウルフラムの研究助手マシュー・クックによって証明されました。 ^[31]

ウルフラムは、A New Kind of Scienceおよび 1980 年代半ばのいくつかの論文で、セルオートマトンとその他のいくつかの単純な計算モデルをその動作に応じて 4 つのクラスに分類できると定義しました。セルオートマトンに関する以前の研究では、特定のルールのパターンの種類を特定しようとする傾向がありましたが、ウルフラムの分類はルール自体を分類する最初の試みでした。複雑さの順にクラスは次のとおりです。

• クラス1: ほぼすべての初期パターンは、安定した均質な状態へと急速に進化します。初期パターンのランダム性は消えます。^[32]
• クラス2: ほぼすべての初期パターンは、安定した構造または振動構造に急速に進化します。初期パターンのランダム性の一部は除去される可能性がありますが、一部は残ります。初期パターンの局所的な変化は、局所的に残る傾向があります。^[32]
• クラス3: ほぼすべての初期パターンは疑似ランダムまたはカオス的に進化します。出現した安定した構造は周囲のノイズによってすぐに破壊されます。初期パターンの局所的な変化は無限に広がる傾向があります。^[32]
• クラス4: ほぼすべての初期パターンは、複雑かつ興味深い方法で相互作用する構造に進化し、長期間存続できるローカル構造が形成されます。^[33]クラス2タイプの安定または振動構造が最終的な結果である可能性がありますが、初期パターンが比較的単純な場合でも、この状態に到達するために必要なステップ数は非常に大きくなる可能性があります。初期パターンのローカルな変更は無制限に広がる可能性があります。 Wolframは、すべてではないにしても、多くのクラス4セルオートマトンが普遍的な計算が可能であると推測しています。これは、ルール110とコンウェイのライフゲームで証明されています。

これらの定義は本質的に定性的であり、解釈の余地がある。ウルフラムによれば、「...ほとんどすべての一般的な分類体系では、ある定義によって 1 つのクラスに割り当てられ、別の定義によって別のクラスに割り当てられるケースが必然的に存在します。セル オートマトンでも同様です。あるクラスの特徴と別のクラスの特徴を示すルールが時々存在します。」^[34]ウルフラムの分類は、セル オートマトンの出力の圧縮された長さのクラスタリングと経験的に一致しています。^[35]

ウルフラムの分類に触発されて、セルオートマトンを形式的に厳密なクラスに分類する試みがいくつか行われてきた。例えば、クリックとユーは3つの明確に定義されたクラス（およびこれらに当てはまらないオートマトンのための4つ目のクラス）を提案した。これらはクリック・ユークラスと呼ばれることもあるが、これらに属するかどうかは決定不可能であることが証明されている。^{[36] [37] [38]} ウルフラムのクラス2は、安定（固定点）ルールと振動（周期的）ルールの2つのサブグループに分けることができる。^[39]

動的システムが4つのクラスに分類されるという考えは、もともとノーベル賞受賞化学者イリヤ・プリゴジンが提唱したもので、彼は熱力学システムを次の4つのクラスに分類した：(1)熱力学的平衡にあるシステム、(2)空間的/時間的に均一なシステム、(3)カオスシステム、(4)散逸構造を持つ複雑な平衡から遠いシステム（プリゴジンの学生ニコリスの1974年の論文の図1を参照）。^[40]

セルオートマトンが可逆的であるとは、セルオートマトンのすべての現在の構成に対して、ちょうど 1 つの過去の構成 (原像) が存在する場合である。^[41]セルオートマトンを構成から構成にマッピングする関数と考えると、可逆性とはこの関数が全単射であることを意味する。^[41]セルオートマトンが可逆的である場合、その時間反転動作もセルオートマトンとして記述できる。この事実は、セルオートマトンを位相的に特徴付けるカーティス・ヘドランド・リンドン定理の結果である。 ^{[42] [43]}すべての構成に原像があるわけではないセルオートマトンの場合、原像のない構成はエデンの園パターンと呼ばれる。^[44]

1次元セルオートマトンの場合、ルールが可逆か不可逆かを決定するアルゴリズムが知られている。^{[45] [46]}しかし、2次元以上のセルオートマトンの場合、可逆性は決定不可能である。つまり、オートマトンルールを入力として受け取り、オートマトンが可逆かどうかを正しく決定することが保証されるアルゴリズムは存在しない。Jarkko Kariによる証明は、 Wang tilesによるタイリング問題に関連している。^[47]

可逆セルオートマトンが熱力学の法則に従うため、ガスや流体の力学などの物理現象をシミュレートするためによく使用されます。このようなセルオートマトンには、可逆になるように特別に構築されたルールがあります。このようなシステムは、トマソ・トフォリ、ノーマン・マーゴラスらによって研究されています。既知の逆を持つ可逆セルオートマトンを明示的に構築するには、いくつかの手法を使用できます。一般的な2つの手法は、2次セルオートマトンとブロックセルオートマトンで、どちらもセルオートマトンの定義を何らかの方法で変更する必要があります。このようなオートマトンが上記の定義を厳密に満たすわけではありませんが、十分に大きな近傍と状態数を持つ従来のセルオートマトンでエミュレートできることが示されており、したがって、従来のセルオートマトンの一部と見なすことができます。逆に、すべての可逆セルオートマトンがブロックセルオートマトンでエミュレートできることが示されています。^{[48] [49]}

セルオートマトンには特別なクラスがあり、トータリスティックセルオートマトンの各セルの状態は数値（通常は有限集合から抽出された整数値）で表され、時刻tにおけるセルの値は時刻t  − 1における近傍のセル（セル自体を含む場合もある）の値の 合計にのみ依存する。 ^{[50] [51]}時刻 tにおけるセルの状態が時刻 t − 1 における自身の状態と近傍の合計の両方に依存する場合、その セルオートマトンを外部トータリスティックセルオートマトンと 呼ぶのが適切である。^[51]コンウェイのライフゲームはセル値が0と 1 である外部トータリスティックセルオートマトンの例である。ライフと同じムーア近傍構造を持つ外部トータリスティックセルオートマトンをライフライクセルオートマトンと呼ぶこともある。^{[52] [53]}

セルオートマトンの概念には、さまざまな一般化が可能です。

一つの方法は、長方形（立方体など）のグリッド以外のものを使用することです。たとえば、平面が正六角形でタイル張りされている場合、それらの六角形をセルとして使用できます。多くの場合、結果として得られるセルオートマトンは、特別に設計された近傍とルールを持つ長方形グリッドを持つものと同等です。別のバリエーションとしては、ペンローズタイルのようにグリッド自体を不規則にすることです。^[54]

また、ルールは決定論的ではなく確率的である場合もあります。このようなセルオートマトンを確率的セルオートマトンと呼びます。確率的ルールは、時刻tにおける各パターンについて、時刻t  + 1 における中央セルが各可能な状態に遷移する確率を示します。より単純なルールが使用される場合もあります。たとえば、「ルールはライフゲームですが、各時間ステップで各セルが反対色に遷移する確率は 0.001% です。」

近傍またはルールは、時間や空間に応じて変化する可能性があります。たとえば、最初はセルの新しい状態は水平方向に隣接するセルによって決定されますが、次の世代では垂直方向のセルが使用されます。

セルオートマトンでは、セルの新しい状態は他のセルの新しい状態によって影響を受けません。これを変更して、たとえば 2 x 2 のセルのブロックを、それ自体とそれに隣接するセルによって決定できるようにすることができます。

連続オートマトンがあります。これらはトータリスティックセルオートマトンに似ていますが、ルールと状態が離散的である代わりに（たとえば、状態 {0,1,2} を使用するテーブル）、連続関数が使用され、状態が連続的になります（通常は[0,1]の値）。場所の状態は、有限個の実数です。特定のセルオートマトンでは、このようにして液体パターンの拡散を生成できます。

連続空間オートマトンには連続した位置がある。位置の状態は有限個の実数である。時間も連続しており、状態は微分方程式に従って変化する。重要な例の1つは反応拡散テクスチャである。これはアラン・チューリングが提案した微分方程式で、化学反応によってシマウマの縞模様やヒョウの斑点がどのように作られるかを説明するものである。 ^[55]これらをセルオートマトンで近似すると、よく似たパターンが生成される。MacLennan [1] は連続空間オートマトンを計算モデルとして考えている。

ライフゲームにおけるグライダーに類似した伝播現象を示す連続空間オートマトンの例が知られている。^[56]

グラフ書き換えオートマトンとは、グラフ書き換えシステムに基づくセルオートマトンを拡張したものである。^[57]

最も単純で非自明なセルオートマトンとは、1次元で、セルごとに2つの状態があり、セルの隣接セルはセルの両側にある隣接セルとして定義されるものです。セルとその2つの隣接セルは3つのセルの近傍を形成するため、近傍には2 ³  = 8通りのパターンが考えられます。ルールは、各パターンについて、セルが次の世代で1になるか0になるかを決定することです。したがって、2 ⁸  = 256通りのルールが考えられます。^[6]

これら 256 個のセルオートマトンは通常、 Wolfram コードで参照されます。これは Wolfram が考案した標準命名規則で、各ルールに 0 から 255 までの番号が与えられます。多数の論文で、256 個のセルオートマトン (多くは自明に同型) の個別のケースが分析され、比較されています。ルール30、ルール 90、ルール 110、およびルール 184 のセルオートマトンが特に興味深いものです。以下の画像は、開始構成が 1 (各画像の上部) と 0 で囲まれたものである場合のルール 30 と 110 の履歴を示しています。ピクセルの各行は、オートマトン履歴の世代を表し、t =0 が最上行です。各ピクセルは、0 の場合は白、1 の場合は黒で色付けされています。

ルール 30 はクラス 3 の動作を示します。つまり、示されているような単純な入力パターンであっても、混沌とした、一見ランダムな履歴につながります。

ルール 110 は、ライフ ゲームと同様に、完全にランダムでも完全に反復的でもない、ウルフラムがクラス 4の動作と呼ぶものを示します。局所的な構造が現れ、複雑に見えるさまざまな方法で相互作用します。 A New Kind of Scienceの開発の過程で、1994 年にウルフラムの研究助手として、マシュー クックは、これらの構造のいくつかが普遍性をサポートするのに十分豊富であることを証明しました。ルール 110 は極めて単純な 1 次元システムであり、特定の動作を実行するように設計するのが難しいため、この結果は興味深いものです。したがって、この結果は、クラス 4 システムは本質的に普遍的である可能性が高いというウルフラムの見解を大いに裏付けています。クックは1998 年にセルラー オートマトンに関するサンタフェ研究所の会議でこの証明を発表しましたが、ウルフラムはA New Kind of Scienceの出版前に証明を発表することを望まなかったため、会議の議事録に証明が含まれることをブロックしました。^[58] 2004年、クックの証明は、クックがそれを思いついてから10年以上経って、ついにウォルフラムの雑誌Complex Systems（第15巻第1号）に掲載されました。ルール110は、いくつかの最も小さな汎用チューリングマシンの基礎となっています。^[59]

基本的なセルオートマトンルールは 8 ビットで指定され、すべての基本的なセルオートマトンルールは8 次元単位ハイパーキューブの頂点に位置すると考えられます。この単位ハイパーキューブは、セルオートマトンルール空間です。次近傍セルオートマトンの場合、ルールは 2 ^{5 = 32 ビットで指定され、セルオートマトンルール空間は 32 次元単位ハイパーキューブです。2 つのルール間の距離は、ハイパーキューブの}辺 に沿って、最初のルールを表す 1 つの頂点から別のルールを表す別の頂点まで移動するために必要なステップ数で定義できます。このルール間の距離は、ハミング距離とも呼ばれます。

セルオートマトンルール空間は、同様の動的動作を持つルールが互いに「近い」かどうかという疑問を抱かせる。2次元平面上に高次元ハイパーキューブをグラフィカルに描くことは依然として困難な作業であり、ハイパーキューブ内のルールの大まかな位置を示す1つの指標は、基本ルールの8ビット文字列（または次近傍ルールの32ビット文字列）内のビット1の数である。ルール空間のこれらのスライスに異なるWolframクラスのルールを描くと、クラス1ルールはビット1の数が少なく、したがって空間の1つの領域に位置する傾向があるのに対し、クラス3ルールはビット1の割合が高い（50％）傾向があることがわかる。^[39]

より大きなセルオートマトンルール空間では、クラス4ルールがクラス1ルールとクラス3ルールの間に位置することが示されています。^{[60]この観察は}「カオスのエッジ」というフレーズの基礎となり、熱力学における相転移を彷彿とさせます。

いくつかの生物学的プロセスはセルオートマトンによって発生したり、シミュレートしたりできます。

単純な状態空間を持つセルオートマトンによってモデル化された生物学的現象の例をいくつか示します。

• Conus属やCymbiola属のような貝殻の模様は、自然のセルオートマトンによって生成される。色素細胞は、貝殻の縁に沿った狭い帯状に存在する。各細胞は、隣接する色素細胞の活性化と抑制の活動に応じて色素を分泌し、数学的規則の自然版に従う。^[61]細胞帯は、ゆっくりと成長するにつれて、貝殻に色の模様を残す。例えば、広く分布する種であるConusの織物は、ウォルフラムの規則30のセルオートマトンに似た模様をしている。 ^[61]
• 植物は細胞オートマトン機構を介してガスの摂取と放出を制御します。葉のそれぞれの気孔は細胞として機能します。^[62]
• 頭足動物の皮膚上の動く波模様は、2つの状態を持つ2次元セルオートマトンでシミュレートすることができ、各状態は拡大した色素胞と収縮した色素胞のいずれかに対応している。^[63]
• 閾値オートマトンがニューロンをシミュレートするために発明されており、認識や学習などの複雑な動作をシミュレートすることができます。^[64]
• 線維芽細胞は細胞オートマトンと類似点があり、各線維芽細胞は隣接する細胞とのみ相互作用する。^[65]

さらに、エージェントの速度の明示的なモデル化を必要とする生物学的現象（例えば、集団細胞移動に関係するもの）は、生物学的格子ガスセルオートマトンなどのより複雑な状態空間とルールを持つセルオートマトンによってモデル化される場合があります。これには、次のような医学的に非常に重要な現象が含まれます。

• 転移性浸潤のさまざまなモードの特徴^[66]
• 悪性癌の発生における異質性の役割^[67]
• 腫瘍増殖中の表現型の切り替え。^[68]

ベロウソフ・ジャボチンスキー反応は、セルオートマトンによってシミュレートできる時空間化学振動子です。1950年代にAMジャボチンスキー（ BPベロウソフの研究を拡張）は、マロン酸、酸性臭素酸塩、セリウム塩の混合物の薄く均一な層を混ぜてそのままにしておくと、同心円や螺旋などの魅力的な幾何学模様が媒体全体に広がることを発見しました。1988年8月号のScientific Americanの「コンピュータレクリエーション」セクションで、^[69] AK Dewdneyは、ビーレフェルト大学（ドイツ）のMartin GerhardtとHeike Schusterによって開発されたセルオートマトン^[70]について説明しました。このオートマトンが生成する波のパターンは、ベロウソフ・ジャボチンスキー反応に似ています。

確率的セルオートマトン（確率セルオートマトン）は、統計物理学や凝縮系物理学において、流体力学や相転移などの現象を研究するために使用される。イジングモデルは典型的な例であり、各セルは「アップ」と「ダウン」と呼ばれる2つの状態のいずれかを取ることができ、磁石の理想的な表現を作成する。モデルのパラメータを調整することにより、同じ状態にあるセルの割合を変えることができ、強磁性体が加熱されるとどのように消磁されるかを説明するのに役立つ。さらに、消磁相転移の研究結果は、液体が気体に蒸発するなど、他の相転移に転用することができ、この便利な相互適用性は普遍性として知られている。^{[71] [72]} 2次元イジングモデルやその普遍性クラスの他のシステムにおける相転移は、深く理解するために共形場理論を必要とするため、特に興味深いものとなっている。 ^[73]物理学で重要であった他のセルオートマトンには、流体の流れをシミュレートする 格子ガスオートマトンがある。

セルオートマトンプロセッサは、CA の概念を物理的に実装したもので、情報を計算的に処理できます。処理要素は、同一のセルの規則的なグリッドに配置されます。グリッドは通常、2 次元または 3 次元の正方形のタイリング、つまりテッセレーションです。他のタイリングも可能ですが、まだ使用されていません。セルの状態は、隣接するセルとの相互作用によってのみ決定されます。遠くにあるセルと直接通信する手段はありません。^[74]このようなセルオートマトンプロセッサアレイ構成の 1 つが、シストリックアレイです。セルの相互作用は、電荷、磁気、振動 (量子スケールのフォノン)、またはその他の物理的に有用な手段を介して行うことができます。これはいくつかの方法で実行できるため、どの要素間にも配線は必要ありません。これは、離れた要素と配線を介して通信できる要素を含むセクションに分割されている、今日のほとんどのコンピューターで使用されているプロセッサ (フォン ノイマン設計) とは非常に異なります。

ルール30はもともと暗号に使用できるブロック暗号として提案された。2次元セルオートマトンを使用して疑似乱数生成器を構築することができる。^[75]

セルオートマトンが公開鍵暗号に提案されている。一方向性関数は有限CAの進化であり、その逆関数を見つけるのは難しいと考えられている。このルールを知れば、誰でも簡単に将来の状態を計算できるが、過去の状態を計算するのは非常に難しいと思われる。セルオートマトンはまた、誤り訂正符号の設計にも応用されている。^[76]

セルオートマトンで解決できるその他の問題には次のものがあります。

• 銃殺隊の同期問題
• 多数派の問題

セルオートマトン（CMA）は、生成音楽^[77]や進化的音楽作曲^[78]、ビデオゲームにおける手続き型地形生成^[79]などに利用されてきた。

具体的なセルオートマトンルールには次のものがあります。

ウィキメディア・コモンズには、セルオートマトンに関連するメディアがあります。

Wikibooksにはセルオートマトンに関する本があります。

• Mirek's Cellebration – 無料の MCell および MJCell セルオートマトン エクスプローラー ソフトウェアとルール ライブラリのホームです。このソフトウェアは、多数の 1D および 2D ルールをサポートしています。このサイトでは、広範なルール辞書と、ルールの例が満載された多数の画像ギャラリーを提供しています。MCell は Windows アプリケーションで、MJCell は Java アプレットです。ソース コードは入手可能です。
• Golly は、フォン ノイマン、Nobili、GOL、その他多数のセル オートマトン システムをサポートしています。Tomas Rokicki と Andrew Trevorrow によって開発されました。これは、フォン ノイマン型の自己複製を実証できる、現在利用可能な唯一のシミュレータです。
• Wolfram Atlas – さまざまな種類の 1 次元セルオートマトンを収録したアトラス。
• コンウェイライフ
• ニュースグループ comp.theory.cell-automata からのセルオートマトン FAQ
• 「近隣調査」（三角形のグリッドと、より大きな近隣 CA に関する議論を含む）
• Cosma Shalizi の Cellular Automata Notebook には、学術的および専門的な参考資料の広範なリストが含まれています。