セル・オートマトンについて | ライフゲーム、ルール30、ルール110 など

4つの基本部品

どのセル・オートマトンも同じ4つの部品からできています。グリッドはセルが存在する空間です。1次元の直線、チェス盤のような2次元の平面、さらには3次元の空間のこともあります。状態はセルがとりうる値です。最も単純な場合、セルは2値で、黒か白、1か0です。近傍は、あるセルに直接影響を与えるセルの集まりです。正方格子では通常、周囲の8つのセルすべてからなるムーア近傍か、北・東・南・西だけのフォン・ノイマン近傍を使います。ルールはオートマトンの頭脳であり、各セルに新しい状態を与えるロジックです。たとえば「自分が生きていても、生きている隣接セルが2つ未満なら、孤独で死ぬ」。すべてのセルが同じ瞬間に同じルールを適用します。

1. コンウェイのライフゲーム

ルール：B3/S23。生きているセルは、生きている隣接セルが2つか3つなら生き残ります。死んだセルはちょうど3つで誕生します。それ以外のセルは、次の世代ではすべて死んでいます。ジョン・コンウェイが1970年に考案し、マーティン・ガードナーが『サイエンティフィック・アメリカン』誌のコラムで紹介して有名になりました。グライダー、振動子、宇宙船が生まれます。同じ年、ビル・ゴスパーが最初のグライダー銃を見つけました。30世代ごとに新しいグライダーを永遠に発射し続けるパターンです。グライダーは信号を運び、論理ゲートのように衝突できるため、ライフゲームは計算を行えます。何よりも、単純なルールから複雑な振る舞いが育つことを示しています。

ライフゲームのゴスパーのグライダー銃。グライダーを斜めに次々と発射している — 330世代後のゴスパーのグライダー銃。PictorX で描画。

2. ルール30

種類：1次元の基本セル・オートマトン。各セルの次の状態は自分自身と両隣の2つのセルで決まり、世代ごとに前の行の下に新しい行として描かれます。スティーブン・ウルフラムが1983年にルール30を発表しました。1つの黒いセルから始めると、カオス的な三角形が育ちます。ルールは決定論的なのにランダムに見え、その中央の列が擬似乱数生成器として使われてきたほどです。同じような三角形は、タガヤサンミナシ（Conus textile）という貝の殻の色素模様にも現れます。

1つの黒いセルから育ったルール30の三角形。右側はカオス的で、左側は縞模様 — 1つの黒いセルから始めたルール30、224世代。PictorX で描画。

3. ルール110

種類：ルール30と同じ1次元の基本セル・オートマトンですが、8つの答えの表が異なります。ルール110は計算万能であることが証明されています。マシュー・クックは、適切な最初の行を与えれば、汎用コンピューターが実行できるどんな計算もエミュレートできることを示しました。繰り返す背景の上を移動し、出会うと相互作用する構造を持ちます。証明はこうした衝突をロジックとして使っています。ごく単純なルールが任意の計算をエミュレートできることを示す例です。

右端の1つのセルから育ったルール110。入れ子の三角形を描きながら左へ広がっていく — 右端の1つの黒いセルから始めたルール110。PictorX で描画。

4. Brian's Brain

状態：オフ、オン（発火）、不応期。ルール：オフのセルは、ちょうど2つの隣接セルがオンならオンになります。オンのセルは不応期になります。不応期のセルはオフになります。ブライアン・シルバーマンが考案しました。セルは発火したあと1世代休まなければならないため、どのパルスもそれまでいた場所から離れ続けます。その結果、自走するパターンの群れが生まれます。神経組織や心筋のような興奮性媒質の波に似ていて、しばしば生き物のように有機的に見えます。

ランダムなパッチから広がる Brian's Brain。発火したセルは黄色、消えていく軌跡は紫 — ランダムなパッチから70世代後の Brian's Brain。消えていく軌跡付き。PictorX で描画。

5. Wireworld

状態：空、電子の頭、電子の尾、導体。ルール：頭は尾になり、尾は導体になり、導体は隣接セルのうちちょうど1つか2つが頭のときに頭になります。空のセルは空のままです。 Wireworld もブライアン・シルバーマンが1987年に考案しました。導体のセルはワイヤーで、頭のあとに尾が続いたものが、ワイヤーに沿って走る電子です。電子回路をシミュレートでき、電子が1つ入ったワイヤーのループはクロック、小さな切り欠きはダイオードになり、数個のセルで論理ゲートができます。その中には完全なコンピューターも作られています。たとえばデヴィッド・ムーアとマーク・オーウェンによる Wireworld コンピューターは、素数を計算します。

2つのクロックループ、2つのダイオード、XOR ゲートからなる Wireworld の回路。黄色のワイヤー上に青と赤の電子 — Wireworld の2つのクロック、2つのダイオード、XOR ゲート。PictorX で描画。

ウルフラムの256のルールと4つのクラス

両隣を持つ1次元のセルが見るパターンは、111から000までの8通りのいずれかです。ルールはそれぞれのパターンに新しい状態を与えるので8ビットになり、基本ルールは 2⁸ = 256 通りあります。8つの答えを2進数として読むと、ルールの名前になります。ルール30は 00011110、ルール110は 01101110 です。スティーブン・ウルフラムは、ルールをその振る舞いによって、秩序からカオスまで分類しました。 1. クラス1は一様な状態に落ち着きます。 2. クラス2は安定した構造か繰り返す構造に落ち着きます。 3. クラス3はルール30のように、カオス的でランダムに見えるままです。 4. クラス4はルール110のように、秩序とカオスの境界で、動いて相互作用する構造を作ります。

難易度ランキング

ライフゲーム ★☆☆☆☆ · ルール30 ★☆☆☆☆ · Brian's Brain ★★☆☆☆ · Wireworld ★★★★☆ · ルール110 ★★★★★。最初の2つは見ているだけで仕組みがわかります。ルール110は動く構造を繰り返しの背景の中に隠しています。

見た目が最も美しいもの

1. Brian's Brain · 2. コンウェイのライフゲーム · 3. ルール30 · 4. ルール110 · 5. Wireworld。

数学的に最も重要なもの

1. ルール110：万能性 · 2. ライフゲーム：万能性と創発 · 3. ルール30：カオスとランダム性 · 4. Wireworld：デジタル論理 · 5. Brian's Brain：興奮性システム。

自然、物理学、暗号の中で

セル・オートマトンは、自然、物理学、暗号における複雑なシステムのシミュレーションに使われています。この考え方は1940年代のスタニスワフ・ウラムとジョン・フォン・ノイマンにさかのぼります。2人はセルのグリッドを使って、自分自身を複製できる機械を設計しました。現実の世界では、一部の貝殻の色素模様にセル・オートマトンを見ることができます。たとえばタガヤサンミナシの三角形はルール30に似ています。また、ホウセキカナヘビのうろこは、セル・オートマトンに近いルールで緑と黒が切り替わります。物理学者はセル・オートマトンを使って、気体の流れ、砂山、森林火災をモデル化します。ルール30は見かけ上ランダムなため、乱数生成器やストリーム暗号の候補になりました。

PictorX で試す

セル・オートマトンを開けば、5つすべてを動かせます。グライダー銃、宇宙船の船団、落ち着くまで1,103世代かかるRペントミノを眺めてみましょう。B36/S23 のような任意のライフゲームのルールや、0から255までの任意の基本ルール番号を入力できます。セルを描いたり消したり、Wireworld の回路に電子を送ったり、端をつなげたり、カラフルモードに切り替えたりできます。PNG を保存するか、キャンバスを PictorX エディターで開けます。

よくある質問

セル・オートマトンとは何ですか？

すべてのセルが状態を持つ、セルのグリッドです。1ステップごとに、すべてのセルが、セルとその近傍だけを見る1つの決まったルールで一斉に更新されます。ルールは単純でも、模様は複雑で予測できないものになりえます。

セル・オートマトンを考案したのは誰ですか？

1940年代にロスアラモスにいたスタニスワフ・ウラムとジョン・フォン・ノイマンです。ジョン・コンウェイのライフゲーム（1970年）がこの考え方を広め、スティーブン・ウルフラムは1980年代に256の基本ルールを研究しました。

チューリング完全なセル・オートマトンはどれですか？

ここにある5つのうち、ルール110とライフゲームは万能であることが証明されており、Wireworld は完全なコンピューターを中に収めることができます。万能とは、適切な初期パターンがあれば、汎用コンピューターにできるどんな計算も実行できるという意味です。

ウルフラムの4つのクラスとは何ですか？

クラス1は一様な状態になって消え、クラス2は安定した構造か繰り返す構造に落ち着き、クラス3はルール30のようにカオス的なままで、クラス4はルール110のように動いて相互作用する構造を作ります。

ルール30はなぜランダムに見えるのですか？

どのステップも決まっていますが、各セルは左隣のセルを残りの2つと、小さな違いをすばやく広げるような方法で混ぜ合わせます。中央の列には単純なパターンが見つかっておらず、そのため乱数の生成に使われてきました。

試してみますか？

ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。

セル・オートマトンを試す