導入
セル オートマトンは、「セル」の規則的なグリッドで構成されており、それぞれのセルには有限のセットから選択された「状態」が含まれており、時間の経過とともに進化する可能性があります。時間t+1におけるセルの状態は、その「近傍」と呼ばれる有限数のセルの時間tにおける状態の関数です。新しい時間単位ごとに、同じルールがグリッド内のすべてのセルに同時に適用され、前の世代に完全に依存する新しい「世代」のセルが生成されます。
数学と理論的コンピューターサイエンスで研究されているセルオートマトンは、離散動的システムモデルであると同時に計算モデルでもあります。セル オートマトンのモデルは、その定義の単純さと、特定の巨視的な動作が到達する複雑さとの間のギャップで注目に値します。つまり、すべてのセルの時間の経過に伴う進化を、システムを定義するローカル ルールに（単純に）還元することはできません。そのため、複雑なシステムの研究における標準モデルの 1 つを構成します。
例
最も単純なセルオートマトン
設計できる最も単純な非自明なセルオートマトンは、2 つの状態 (「0」または「1」) のみを取ることができるセルの 1 次元グリッドで構成され、各セルの近傍はそれ自体と 2 つのセルから構成されます。それに隣接するセル。
各セルは 2 つの状態を取ることができ、そのような近傍には 2 3 =8 通りの構成 (またはパターン) が考えられます。セル オートマトンが機能するためには、これらのパターンごとに、次世代のセルの状態がどうあるべきかを定義する必要があります。これを行うには 2 8 =256 通りの異なる方法があるため、このタイプのセル オートマトンは 256 通りになります。
この系統のオートマトンは「エレメンタリー」と呼ばれます。多くの場合、これらは 0 ～ 255 の整数で指定され、そのバイナリ表現は、連続するパターン 111、110、101 などでオートマトンがとる一連の状態になります。
例として、次の表で定義されるセル オートマトンを考えてみましょう。これは進化規則を示しています。
| 当初の動機 | 111 | 110 | 101 | 100 | 011 | 010 | 001 | 000 |
|---|---|---|---|---|---|---|---|---|
| 中央セルの次の値 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 |
(これは、たとえば、特定の時刻tでセルが状態 “1” にあり、その左隣のセルが状態 “1” で、右隣のセルが状態 “0” である場合、時刻t+1ではセルは状態は「0」です。）
1 つを除くすべてのセルが状態「0」である最初のグリッドから開始すると、次のようになります。
ここで、各行は前の行の結果です。
慣例により、このルールは「ルール 30」と呼ばれます。30 は 2 進数で 00011110 と書かれ、00011110 は進化の法則を表す上記の表の 2 行目であるためです。
人生ゲーム
「ライフ ゲーム」は 2 次元のセル オートマトンであり、各セルが 2 つの値 (「0」または「1」ですが、私たちはむしろ「生きている」または「死んでいる」について話します) を取ることができ、その将来の状態がどこにあるのかを示します。現在の状態と、周囲の 8 つの細胞のうちの生きている細胞の数によって決まります。
- 細胞が生きていて、2 つまたは 3 つの生きた細胞に囲まれている場合、その細胞は次の世代まで生き続けますが、そうでない場合は死にます。
- 細胞が死んでいて、ちょうど 3 つの生きた細胞に囲まれている場合、その細胞は次の世代で生まれます。
これらのルールは単純に見えますが、非常に複雑な問題を引き起こします。
同じ原理で、誕生または生存のしきい値を変更したり、状態を追加したりすることによって、多数のルールを想像できます。これらのバリエーションの中で、次のものが挙げられます。
- 昼と夜
- ハイライフ
- 移民
- クアッドライフ
セルの状態の変化を決定するために考慮されるセルのすぐ隣のセルのみを考慮するものもありますが、半径 2 ボックス以内、またはそれ以上の範囲内にある隣接セルの状態も考慮するものもあります。また、特定の近傍ボックスに他のボックスよりも大きな重みを割り当てるものもあります ( WeightedLife )。
他のみんなは…
セル オートマトンを定義するために考えられるルールは、州の数が少なく、近隣が小さい場合でも、非常に多数あります。
| 2つの州 | 3つの州 | 4つの州 | 5つの州 | |
|---|---|---|---|---|
| 2 隣人 | 16 | 19,683 | 4,294,967,296 | > 10 17 |
| 3 隣人 | 256 | 7,625,597,484,987 | > 10 38 | > 10 87 |
| 4人の隣人 | 65,536 | > 10 38 | > 10,154 | > 10,436 |
| 5人の隣人 | 4,294,967,296 | > 10,115 | > 10,616 | > 10 2184 |
| 6人の隣人 | > 10 19 | > 10,347 | > 10 2466 | > 10 10921 |
したがって、セル オートマトンのモデルは、広大な探求の余地を提供します。セル オートマトン シミュレーターをプログラムするのは難しくなく、 Web には多かれ少なかれ成功した作品が溢れています。たとえば、Mirek Wojtowicz のサイト、Mirek’s Cellebration では、シミュレーションソフトウェアと非常に豊富な例のギャラリーが提供されています。興味深いシミュレーターのもう 1 つの例は Golly です。これは主にライフ ゲーム専用であり、クアッドツリーとハッシュを組み合わせて使用することでこのオートマトン用に最適化されています。