1次元セルオートマトン シミュレータ - 全256ルール一覧・解説つき

1. 初期状態を用意する

  1列のセルが並んでいて、それぞれ 0 か 1 の状態を持つ。

  世代0: [0] [0] [1] [0] [0]

2. 各セルの近傍を見る

  セルごとに、左隣・自分・右隣の3つをセットで見る。
  端のセルは反対側とつながったリング状として扱う（周期境界条件）。

       左 中 右
        ↓  ↓  ↓
  [0]  [0][1][0]  [0]

3. ルールテーブルで次の状態を引く

  3つの組み合わせをルールテーブルに照合して、次の世代のそのセルの値を決める。

  例: Rule 110の場合
  (0,1,0) → ルールテーブル参照 → 1

4. 全セル同時に更新する

  これを全セルに対して同時に適用して、次の世代を作る。

  例: Rule 110の場合
  世代0: [0] [0] [1] [0] [0]
                ↓ 全セル同時に遷移
  世代1: [0] [1] [1] [0] [0]

5. 繰り返す

  2→3→4を繰り返して世代を重ねていく。2Dに並べると模様ができる。

1次元セルオートマトン（Elementary Cellular Automaton, ECA）は、スティーブン・ウルフラムが1980年代に体系的に研究した最もシンプルなセル・オートマトンです。ウルフラムはセル・オートマトンの振る舞いをクラス1（均一）、クラス2（周期的）、クラス3（カオス）、クラス4（複雑系）の4つに分類しました。クラス1・2は秩序的、クラス3はカオス的な振る舞いを示し、クラス4はその境界に位置します。

256通りのルールの中には、カオス的な乱数生成に使われるRule 30、チューリング完全が証明されたRule 110、シェルピンスキーのガスケットを生成するRule 90、交通流モデルとして知られるRule 184など、興味深い性質を持つルールが数多く存在します。

セル・オートマトンの歴史や応用分野について詳しくはこちら →

上述の4クラスのうち、クラス3（カオス）とクラス4（複雑系）は特に興味深い挙動を示します。

クラス3 — カオス

ランダムに見える非周期的なパターンを生成します。Rule 30 はMathematicaの乱数生成に使われたことで有名で、等価ルールの Rule 86（左右反転）、Rule 135（reverse+flip）、Rule 149（左右反転+reverse+flip）も同じ構造のカオスを示します。Rule 45、Rule 106 もカオス的な挙動を示し、それぞれ等価ルール群（Rule 45 → 75, 89, 101、Rule 106 → 120, 169, 225）を持ちます。

クラス4 — 複雑系

秩序的なクラス1・2とカオス的なクラス3の境界に位置します。完全に規則的でもなく、完全にランダムでもない振る舞いの中から、「グライダー」と呼ばれる移動する局所構造が自然に出現し、互いに衝突・相互作用します。この性質が計算能力につながっており、詳しくは次のセクションで解説します。

チューリング完全とは、適切な初期条件を与えれば任意の計算を実行できる能力のことです。クラス4（複雑系）の「秩序的すぎず、カオス的すぎない」性質がこれを可能にしています。秩序的なルールでは情報が固定されてしまい、カオス的なルールでは情報が拡散して消えてしまいますが、クラス4ではグライダーによって情報を保持・伝達できるため、計算が成り立ちます。

Rule 110

2004年にMatthew Cookによってチューリング完全であることが証明され、この極めて単純なルールがあらゆる計算をシミュレートできることが示されました。グライダーと呼ばれる移動する局所構造が衝突・相互作用することで計算を実現します。等価ルールの Rule 124（左右反転）、Rule 137（reverse+flip）、Rule 193（左右反転+reverse+flip）もすべてチューリング完全です。

Rule 54

チューリング完全の有力候補です。Rule 110 と同様にグライダーを持ちますが、証明はまだ完了していません。シングルセルの初期条件では左右対称な出力を生成します。左右反転（後述）しても Rule 54 自身になるため、等価ルールは Rule 147（reverse+flip）のみです。

ECAの中で最も有名なパターンのひとつがシェルピンスキーのガスケット（Sierpinski triangle）です。1つのセルだけをONにした初期条件から、自己相似的なフラクタル三角形が生成されます。

正統なシェルピンスキー

Rule 18, 90, 146 は左右対称のシェルピンスキー三角形を生成します。Rule 60 は右に傾いた三角形、Rule 102 は左に傾いた三角形を生成します（この2つは左右反転の関係）。

シングルセルでのみシェルピンスキー

Rule 26, 154, 210, 218 はシングルセルの初期条件ではシェルピンスキー三角形を生成しますが、ランダムな初期条件ではそれぞれ異なる挙動を示します。

シェルピンスキー風フラクタル

Rule 22, 122, 126 はシェルピンスキーに似たフラクタルパターンを生成しますが、厳密にはシェルピンスキー三角形とは異なります。

白黒反転シェルピンスキー

シェルピンスキーを生成する Rule 60, 90, 102 は回文ルール（後述）で、それぞれ等価ルールの Rule 195, 165, 153 が白黒反転したシェルピンスキーを生成します。同じく回文ルールの Rule 126（シェルピンスキー風）の等価ルール Rule 129 は、反転シェルピンスキー風フラクタルを生成します。

その他の等価なシェルピンスキー

Rule 18 の reverse+flip（後述）である Rule 183、Rule 146 の reverse+flip である Rule 182 も等価なシェルピンスキーを生成します。

Rule 184 は粒子保存則を持つルールで、交通流のシミュレーションに使われます。黒セルを車、白セルを空きスペースとみなすと、車は前方が空いていれば1マス前進し、詰まっていれば停止します。等価ルールの Rule 226（左右反転）は逆方向の交通モデルになります。

256個のルールの中には、同じ構造のパターンを生成する「等価ルール」が存在します。等価ルールは以下の3つの変換で結ばれています。

左右反転（mirror）

近傍パターンの左セル(p)と右セル(r)を入れ替える操作です。例えば 110（左=1,中=1,右=0）は 011（左=0,中=1,右=1）になります。対称なパターン（111, 101, 010, 000）は変化しません。結果としてビット位置 6↔3 と 4↔1 の値がswapされ、同じ初期条件から左右逆のパターンが出力されます。シングルセルからの出力が左右対称なルール（例: Rule 26と82、Rule 30と86）では左右反転しても同じに見えるため、ランダム初期条件で確認してください。

reverse+flip

ビット列を逆順に並べ替えてから、0と1を入れ替える操作です。初期条件も白黒反転すると、出力も白黒反転した同じパターンになります。ただし Rule 110 と Rule 137 のように、回文ルールでなくてもシングルセルの初期条件で白黒反転したパターンが現れるケースもあります。

左右反転 + reverse+flip

上記2つの変換を組み合わせた操作です。近傍パターンの左右を入れ替えたあと、ビット列を逆順にして0と1を反転させます。

注意 mirror（左右反転）とreverse+flipのreverseは異なる操作です。mirrorは近傍パターンの左右セルを入れ替える操作（ビット位置 6↔3, 4↔1 のswap）で、reverseはビット列全体の順序を逆にする操作です。

ルールのビット列が回文（左右どちらから読んでも同じ配列）の場合、255-R（各ビットの0と1を入れ替えるだけ）で等価ルールになります。例えばRule 90（01011010）は回文なので、255-R のRule 165（10100101）と等価です。回文ルールではreverse+flipもビット反転と同じ結果になります（reverseしても変わらないため）。