前のページ 1/4 次のページ

セル・オートマトン (Cellular automaton, CA) とは、格子状のセルと単純な規則からなる、離散的計算モデルである。計算可能性理論、数学、理論生物学などの研究で利用される。非常に単純化されたモデルであるが、生命現象、結晶の成長、乱流といった複雑な自然現象を模した、驚くほどに豊かな結果を与えてくれる。

正確な発音に近い"セルラ・オートマトン"とも呼ばれることがある。"セル"は「細胞」「小部屋」、"セルラ"は「細胞状の」、オートマトン(複数形オートマタ)は「からくり」「自動機械」を意味する。複数形はセルラ・オートマタ (cellular automata) である。

セル・オートマトンは無限に広がる格子状のセル(細胞のような単位)で構成されており、各セルは有限種類の(多くは2〜数十種類の)内部状態を持ち、時間が進むと共に内部状態は変化していく。また、ここでの時間は離散的(不連続的)なものであり、時刻 t + 1 における1つのセルの内部状態は、時刻 t における、そのセル自体および近傍のセルの内部状態によって決定される。全てのセルに等しく「規則」が適用され、セルが更新されると、新たな「ジェネレーション」(世代)になった、と考える。

◆概要

2次元の(つまり面状の)セル・オートマトンの例として、無限に広がる方眼紙を考える。方眼紙のひとつのマス目がセルにあたる。それぞれのセルは「黒」と「白」の2つの内部状態をもつ。あるセルの近傍には8つのセル (ムーア近傍) が隣接している。これら9つのセルが取ることができる状態は全部で2⁹ = 512個存在する。セル・オートマトンがどのように時間発展していくかのルールは表として与えられる。すなわち次の時間ステップ(t+1)で、中心のセルが「黒」「白」いずれになるかは、現在の時間ステップ(t)でとり得る512個のパターンそれぞれについての一覧表によって決定される。

2次元のセル・オートマトンで最も有名なものがライフゲームである。ライフゲームは以下のようなルールで記述される。

・ 誕生: 死んでいるセル(「白」)の周囲に3つの生きているセル(「黒」)があれば次の時間ステップでは生きる(「黒」になる)。

・ 維持: 生きているセル(「黒」)の周囲に2つか3つの生きているセル(「黒」)があれば次の世代でも生き残る(「黒」のままである)。

・ 死亡: 上以外の場合には次の世代では死ぬ(「白」になる)。

このライフゲームのルールは細菌などの生物の繁殖のアナロジーである。すなわち、孤独でも人口過密でも死んでしまう。最も快適な人口密度では子孫を残し繁栄するというものである。実際ライフゲームは生物の増殖のような複雑で多様な振舞いを示す。

一般に、各セルは同じ状態から開始し、一部の有限個のセルだけがそれ以外の状態から開始する。これを「コンフィギュレーション」と呼ぶ。また、全体が周期的なパターンを形成していて、一部がそのパターンから外れた状態で開始するということもある。後者は1次元のセル・オートマトンでは一般的である。

セル・オートマトンのシミュレーションには有限の格子を使うことが多い。2次元の場合、無限の平面ではなく、有限の四角形で表される。有限の格子での明らかな問題は端のセルをどう扱うかである。端をどう扱うかが格子全体のセルの状態に影響を与える。1つの手法は、端のセルを全て変化しない定数を状態として持つとするものである。別の手法は端のセルの近傍を一般のセルとは違う内容にするというものである。つまり、端のセルの近傍を通常より少なく定義することもできるが、その場合は規則も新たに定義しなければならない。別の手法として、2次元の場合に四角形の平面の端の上下と左右を繋げて、トーラス形にすることもある。これは、ある意味で無限の平面が同じ四角形で平面充填されていることになる。1次元であれば、線の端を繋いでループにすることになる。

◆ セル・オートマトンの歴史

1940年代にロスアラモス国立研究所で働いていたスタニスワフ・ウラムは結晶の成長について研究していたとき、モデルとして単純な格子ネットワークを使用していた。同じころロスアラモスで一緒に働いていたジョン・フォン・ノイマンは自己複製機械を研究していた。フォン・ノイマンはまず、あるロボットの記述に基づいて別のロボットの記述を行うという設計を考えていた。この設計は運動学モデル(Kinematic model)と呼ばれている。設計を進めるに連れ、フォン・ノイマンは、複製を作るための「部品の海」をロボットに与えることのコストの膨大さやあるロボットが別のロボットを作るということを記述する大変さを徐々に理解していった。ウラムはフォン・ノイマンに数学的に抽象化した設計を示唆し、自身が結晶の成長で使ったモデルを紹介した。これが元となってセル・オートマトンが生まれた。ウラムの格子ネットワークのように、フォン・ノイマンのセル・オートマトンは2次元で、その中に自己複製機械がアルゴリズム的に埋め込まれた。これがUniversal Copier and Constructor(UCC)であり、近傍として隣接する4つのセルのみ(ノイマン近傍)を考慮し、1つのセルあたり29の内部状態を持っている。このモデルで彼は自己複製機械として動作するパターンをデザインし、それが無限に自己複製を繰り返すことを数学的に証明した。この設計は平面充填モデルとして知られている。

1968年、エドガー・F・コッドは 8 状態で自己複製を繰り返すコッドのセル・オートマトンを考案した。

1970年代、2状態で2次元のセル・オートマトンであるライフゲームが特にコンピュータコミュニティでよく知られるようになった。ジョン・コンウェイの発明によるもので、マーティン・ガードナーが Scientific American 誌(日本では日経サイエンス誌)で紹介したことで有名となったのである。ライフゲームは単純だが、システムとして興味深い挙動を示し、ランダム性と規則性の間で変動する。ライフゲームの最も顕著な特徴として「グライダー」(格子を横断して移動していくセル群)が頻繁に発生することが挙げられる。グライダーをうまく配置すると一種の相互作用が生まれる。長年の研究により、ライフゲームがチューリングマシンをエミュレートできることが判明した。それが単なる趣味の話題と受け止められたためか、ライフゲームの特殊性の研究や関連する規則の研究が若干行われた以外、この発見を受けた研究はなされなかった。

しかし1969年、ドイツのコンピュータのパイオニアの一人であるコンラッド・ツーゼは、著書 Calculating Space の中で、宇宙の物理法則は本質的には離散的であり、宇宙全体が一種の巨大なセル・オートマトン上の決定的な計算の結果であると主張した。この著書が今日デジタル物理学と呼ばれている分野の基礎を築いた。

1983年、スティーブン・ウルフラムは、非常に基本的だが未知のセル・オートマトン(elementally cellular automata)に関する研究論文を次々と発表し始めた。ウルフラムは、単純な規則で示される振る舞いの予期せぬ複雑さを見て、自然界の複雑さも同様の機構によって生まれているのではないかと考えた。さらにウルフラムは真の無作為性と計算既約性の概念を定式化し、ルール110がチューリング完全であると推測した(1990年代に Matthew Cook がそれを証明した)。

ウルフラムはあらゆる1次元のセル・オートマトンの時間発展の仕方を調べ上げ、以下の4つのクラスに分類した。

・ クラス1 - セル全体が同じ状態になり、変化しなくなる。:秩序状態

・ クラス2 - セルの時間発展につれ、最終的に周期的な変化になる。:秩序状態

前のページ 1/4 次のページ

・セル・オートマトン page1

・セル・オートマトン page2

・セル・オートマトン page3

・セル・オートマトン page4