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年代に体系的に研究した最もシンプルなセル・オートマトンです。わずか256通りのルールしかないにもかかわらず、その振る舞いは驚くほど多様で、ウルフラムはこれを4つのクラスに分類しました。

クラス1 — 均一

どんな初期条件から始めても数世代で全セルが同じ状態に収束します。初期条件の情報が完全に失われる、最も単純な振る舞いです。

クラス2 — 周期的

ストライプや固定点のような安定したパターンに落ち着き、それを繰り返します。初期条件の影響は局所的に残りますが、全体としては予測可能な秩序に収まります。

クラス3 — カオス

ランダムに見える非周期的なパターンを際限なく生成し続けます。初期条件のわずかな違いが全く異なる結果を生み、長期的な予測はできません。しかし決定論的なルールから生成されるため、擬似乱数として応用できるという面白い性質を持っています。

クラス4 — 複雑系

秩序（クラス1・2）とカオス（クラス3）のちょうど境界に位置します。クラス1・2のように情報が固定されてしまうこともなく、クラス3のように情報が拡散して消えてしまうこともありません。この絶妙なバランスの中で、「グライダー」と呼ばれる形を保ったまま移動する構造が自然に出現します。グライダーは情報を運ぶことができ、グライダー同士の衝突で新しいパターンが生まれます。この「情報を保持しながら伝達・変換できる」性質が、計算と同じ仕組みを実現しています。

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

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

クラス1では、Rule 0（すべて0に収束）やRule 255（すべて1に収束）のように、数世代で全セルが同じ状態になります。一方、クラス2には興味深いルールが多数あります。フラクタル模様を生成するシェルピンスキー系ルールや、交通流をシミュレートするルールなどが代表的です。

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

正統なシェルピンスキー

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

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

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

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

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

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

ランダムに見える非周期的なパターンを生成します。Rule 30 はMathematicaの乱数生成に使われたことで有名です。Rule 45、Rule 106 もカオス的な挙動を示します。

上で説明した「グライダー」は、クラス4のルールをシミュレータで実行すると実際に観察できます。Rule 110やRule 54では、背景の周期的パターンの中を形を保ったまま移動する構造が現れ、異なる速度のグライダー同士が衝突すると消滅・合体・分裂といった複雑な相互作用を引き起こします。

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

Rule 110

2004年にMatthew Cookによってチューリング完全であることが証明され、この極めて単純なルールがあらゆる計算をシミュレートできることが示されました。

Rule 54

チューリング完全の有力候補です。Rule 110 と同様にグライダーを持ちますが、証明はまだ完了していません。シングルセルの初期条件では左右対称な出力を生成します。

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

左右対称

近傍パターンの左セルと右セルを入れ替える操作（swap）を行うと、左右対称なパターンが得られます。シングルセルからの出力が左右対称なルール（例: Rule 26と82、Rule 30と86）では変換しても同じに見えるため、ランダム初期条件で確認してください。

白黒対称

ビット列を逆順に並べ替えてから0と1を入れ替える操作（reverse+flip）を行うと、白黒対称なパターンが得られます。単純なビット反転（complement）とは異なります。初期条件も白黒反転すると、出力も白黒反転した同じパターンになります。ただし Rule 110 と Rule 137 のように、シングルセルの初期条件で白黒反転したパターンが現れるケースもあります。

左右対称 + 白黒対称

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

白黒対称の特殊ケース — ルールが回文の場合

ルールのビット列が回文（左右どちらから読んでも同じ配列）の場合、入力のビットを反転するだけで出力もビット反転されます。通常の白黒対称では reverse+flip（逆順+反転）が必要ですが、回文ルールではビット列が逆順にしても変わらないため、flip（反転）だけで白黒対称が成り立ちます。例えば Rule 90（01011010）は回文なので、255 - 90 = Rule 165（10100101）と等価です。

注意 左右対称のswapは、近傍パターン（3ビット）の左右を入れ替える操作です。例えば近傍パターン 110（位置6）の左右を入れ替えると 011（位置3）になるため、ルールのビット列（8ビット）ではビット位置6と3の値が入れ替わります。同様に 100（位置4）と 001（位置1）も入れ替わります。対称なパターン（111, 101, 010, 000）は左右を入れ替えても変わりません。例えば Rule 110（01101110）の場合、ビット位置6と3の値（どちらも1）はそのまま、ビット位置4の値（0）と位置1の値（1）が入れ替わり、01111100 = Rule 124 になります。

上記の3つの等価変換を適用すると、256個のECAルールは88個の独立な代表ルールに集約されます。残りのすべてのルールは、これらのいずれかと等価です。