単純な規則から複雑な現象を生み出すセル・オートマトン。
セル・オートマトン(Cellular Automata)は任意次元の空間内で単純な規則を用いて反復計算を繰り返す計算モデルである。数個の単純な規則から鮮やかな模様や複雑な自然現象模した動きを実現する。
セル・オートマトンのアイデアはフォン・ノイマンによって考案され、その後数学者のジョン・ホートン・コンウェーによって以下に紹介するライフゲームが生み出された。
HTML5のCanvasで作られた新しいページ、藍手箱 セル・オートマトンがあります。新しい技術が使用できる最新ブラウザを推奨。
2次元のセル・オートマトンで最も有名なのがライフゲームである。まず無限に広がる方眼紙を考える。この方眼紙は黒(生)と白(死)の2つの状態を取りうるものとする。この方眼紙の全てのセルをそれぞれ次の3つ規則で操作していく。
これは生物の増殖を模したものだ。過密すぎても過疎過ぎても生物は死に絶え、最適な環境(2か3)の時のみ生きていくことができる。実際このライフゲームは生物の増殖に近い複雑な動作をする。
以下にJavaScriptで実際に動くライフゲームを作成した。無限の方眼紙を作成することは不可能なので、有限だが端がない方眼紙をフィールドとしている。具体的には上下左右をそれぞれ反対側とつなげ、端をなくしている。
試したブラウザではOpera8が最も速く処理を実行した。Operaなら60*60=3600マスのフィールドでライフゲームを実行できる。
ライフゲームをさらに簡素化したものが1次元セル・オートマトンである。2次元セル・オートマトンのモデルは簡素であるが考えられる組み合わせが余りに多すぎる。1次元セル・オートマトンではたかが256通りの組み合わせしかない。
1次元セル・オートマトンは自身と左右のセルの合計3つのセルによって決定される。3つのセルの取りうる組み合わせは8パターンあり、その結果として返るセルは白か黒の2通り、つまり28=256通りである。2次元セル・オートマトンでは全世代を一度に表示するには3次元の図が必要であった。しかし1次元セル・オートマトンでは全ての世代を重ね合わせた図は2次元になる。つまり1世代目からn世代目までを一目で見渡すことができる。
以下はJavaScriptによる1次元セル・オートマトンである。1〜256の規則番号によって描画される結果が大きく異なってくる。また初期世代を1点固定にすることができる。例えば規則番号90番で一点固定をチェックして描画すると美しいフラクタル図形が描かれる。
(2008/08/02)近傍2マスまで広げクラス4の複雑性を実行できるタイプのデモを公開。
256パターンある1次元セル・オートマトンを調べたスティーブン・ウォルフラムはこれを4つのクラスに分類した。
有限の世代内に真っ黒若しくは真っ白に収束するタイプ。
若い世代はバラバラでも世代を重ねると安定した模様に落ち着くタイプ。
白と黒がバラバラに出現するタイプ。ほぼランダムなカオス状態。
3つのクラスにも分類できない。安定状態に収束せず、またカオス状態ともいえないタイプ。自然の複雑系はこのクラス4から成り立っていると考えられている。
※256パターン内にもこれに近い振る舞いをするものがあるが、クラス4は近傍2マスまで範囲を広げないと得られないとされる。