セル・オートマトン

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

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

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

概要

2次元の(つまり面状の)セル・オートマトンの例として、無限に広がる方眼紙を考える。方眼紙のひとつのマス目がセルにあたる。それぞれのセルは「黒」と「白」の2つの内部状態をもつ。あるセルの近傍には8つのセル (ムーア近傍) が隣接している。これら9つのセルが取ることができる状態は全部で29 = 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年スティーブン・ウルフラムは、非常に基本的だが未知のセル・オートマトン(elementary cellular automata)に関する研究論文を次々と発表し始めた。ウルフラムは、単純な規則で示される振る舞いの予期せぬ複雑さを見て、自然界の複雑さも同様の機構によって生まれているのではないかと考えた。さらにウルフラムは真の無作為性と計算既約性の概念を定式化し、ルール110チューリング完全であると推測した(1990年代に Matthew Cook がそれを証明した)。

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

  • クラス1 - セル全体が同じ状態になり、変化しなくなる。:秩序状態
  • クラス2 - セルの時間発展につれ、最終的に周期的な変化になる。:秩序状態
  • クラス3 - セル全体がランダムな変化を続ける。:カオス状態
  • クラス4 - 規則的なパターンとランダムなパターンが共存し、複雑なパターンを形成する。

秩序状態であるクラス1クラス2は新しい変化を生み出さない、いわば死んだ世界である。カオス状態であるクラス3はランダムすぎて、意味のある情報を生み出すことができない。ウルフラムは秩序状態とカオス状態の間にあるクラス4の様な状態こそが、生命現象などの現実世界で見られる複雑な現象を引き起こす源だと考えた。この研究により、複雑系と呼ばれる新しい科学分野の基盤が確立した。

ウルフラムは1980年代中盤以降に学界を去ってMathematicaを開発し、彼のそれまでの研究結果を広い範囲の単純で抽象的な系に拡張して適用するのに Mathematica を使った。2002年、ウルフラムはそれらの成果を 1280頁の著書 A New Kind of Science として発表した。この中でセル・オートマトンがあらゆる科学にとって重要な関わりを持つことを主張している。一部で誤解されているように、同書は物理法則がセル・オートマトンに基づいているとは言っていない(ツーゼとは異なる)が、セル・オートマトンに基づいた物理モデルをいくつか記述しており、他にも各種抽象系に基づいたモデルを示している。

1次元セル・オートマトンの例

1次元セル・オートマトンは、線状(ひも状)であり、あるセルに隣接するセルは2個であり、セル・オートマトンの中でも最もシンプルなものである。

ルール30

以下に「ルール30」と分類される1次元セル・オートマトンの例を示す。

  • 「ルール30」と呼ばれるのは、時刻t+1における中央のセルの内部状態一覧を並べると0,0,0,1,1,1,1,0となっており、この2進数の数を10進数に直すと30であるためである。このようにして28 = 256通りある1次元セル・オートマトンのルールを分類しているのである。
ルール 30
時刻tでの内部状態(左、中央、右) 111 110 101 100 011 010 001 000
時刻t+1での中央のセルの内部状態 0 0 0 1 1 1 1 0


下図は、最初の内部状態が1である1個のセルが、時間とともに発展する様子である。(線状のセルを、時間順に、下方へと並べている)

CA.1D.Rule30.Early generation.png


下図は、さらに時間が経過した様子。

CA rule30s.png
セル・オートマトン状模様の貝殻(イモ貝)

複雑で自己反復的な三角形の模様を作り出している。これはクラス4の典型的な振舞いである。 ウルフラムはこのパターンが、ある種の貝殻の表面にある模様に大変よく似ていることに気づき、セル・オートマトンこそが複雑な自然現象を説明するために重要な鍵を握っていると考えた。

ルール90

また、ルール90の1次元セル・オートマトンは典型的なフラクタル図形であるシェルピンスキーのギャスケットを生成する。

シェルピンスキーのギャスケット
ルール 90
時刻tでの内部状態 111 110 101 100 011 010 001 000
時刻t+1での中央のセルの内部状態 0 1 0 1 1 0 1 0


可逆型セル・オートマトン

現在状態から1つ前の状態(プレイメージ)が一意に求められるセル・オートマトンを「可逆的; reversible」であるという。セル・オートマトンを状態から状態への関数と考えると、可逆性はその関数が全単射であることを意味する。

1次元のセル・オートマトンについては、プレイメージを探すアルゴリズムが知られていて、各ルールについて可逆的かそうでないかは既に判明している。2次元以上のセル・オートマトンについては、任意のルールの可逆性は判定不能であることが証明されている。Jarkko Kari による証明は、ワンのタイルのタイル並べ問題と関連している。

可逆型セル・オートマトンは、熱力学の法則に従う気体や液体の力学現象のシミュレーションに使われることが多い。その場合のセル・オートマトンは特別に可逆性を持つよう設計される。

可逆でない有限のセル・オートマトンには、どんな状態からも絶対生成(到達)できない配置が存在する。そのような配置を「エデンの園配置」と呼ぶ。換言すれば、エデンの園パターンにはプレイメージが存在しない。

意識的に可逆型セル・オートマトンを作る手法はいくつか存在する。二階セル・オートマトンブロック・セル・オートマトンがそれで、どちらもセル・オートマトンの定義に何らかの修正を施す。これらは厳密には上に挙げたようなセル・オートマトンの定義から外れているが、十分に大きな近傍と多数の状態を持つ従来型のセル・オートマトンでエミュレートできることが判っており、従来型のセル・オートマトンのサブセットと見なすことができる。

総和型セル・オートマトン

特殊なセル・オートマトンとして、総和型(totalistic)セル・オートマトンがある。総和型セル・オートマトンでの各セルの状態は数値で表され(通常、有限の整数値の集合)、時刻 t におけるセルの値は、時刻 t−1 における近傍(自身も含むこともある)のセル群の値の総和だけに依存して決定される。時刻 t におけるセルの状態が自身の t−1 での状態に依存する場合、そのようなセル・オートマトンを「外部総和型; outer totalistic」と呼ぶ。ライフゲームは、値として 0 と 1 をとる外部総和型セル・オートマトンの例である。

暗号への応用

ルール30は、ストリーム暗号に応用可能ではないかと言われていた。

セル・オートマトンを公開鍵暗号に使うことも提案されてきた。有限なセル・オートマトンの変化は一方向性関数と考えられ、その逆関数を見つけることは困難と考えられているためである。ルールを与えられると、誰でも簡単に次の状態を計算することはできるが、現在状態から以前の状態を求めることは非常に難しい。しかし、ルール設計者は容易に逆関数を求める方法を作ることができる。従って、これは一種の落とし戸関数であり、公開鍵暗号に活用できる。このような原理に基づいたセキュリティシステムは今のところ知られていない。

化学における例

ベロウソフ・ジャボチンスキー反応はセル・オートマトンを使ってシミュレートできる。1950年代、A・M・ジャボチンスキーはソ連B・P・ベロウソフの研究成果をさらに進め、マロン酸、酸化した臭素酸塩、セリウムの混合物の薄い均一な層を置いておくと、同心円や渦巻き模様などの幾何学的模様が生じることを発見した。1988年8月、Scientific American (日本では日経サイエンス)誌上の "Computer Recreation" という記事で、A. K. Dewdney はベロウソフ・ジャボチンスキー反応に非常によく似た挙動を示すセル・オートマトンを紹介した。ベロウソフ・ジャボチンスキー反応が、分子レベルでそのセル・オートマトンと同じような仕組みで発生しているのかどうかは不明である。これまで、セル・オートマトン的な化学反応が自然界で観察されたことはない。そのような化学反応は全て研究室や実験室でのみ観測されている。

並列コンピュータとの類似と応用

離散的(非連続的)時間で記述され、時刻t+1における1つのセルの内部状態は、時刻tにおける状態によって決定されるといった点で、セル・オートマトンはチューリングマシンとよく似ている。実際、万能チューリングマシンと等価な動作をするセル・オートマトンが存在することが知られている。しかし、チューリングマシンは「逐次的な処理を行うデジタルコンピュータ」のモデルであるのに対し、セル・オートマトンは各セルが並列に演算処理を実現しており、いわば "並列コンピュータ" であるという点で大きく異なる。

セル・オートマトンの概念をハードウェアで実装して情報処理を行おうとする試みも行われている。処理要素は格子状に配置され、2次元か3次元の平面充填構造とされる。それ以外の並べ方も可能だが、まだ試されたことはない。各処理要素(すなわちセル)は隣接する少数のセルだけとやり取りする。遠いセルとの直接通信手段は存在しない。セルの相互作用には、電荷、磁化、振動などの物理的な手段を使う。いずれにしても各処理要素間を結線する必要はない。これは、今日のノイマン型コンピュータのプロセッサとはかなり違う。

誤り訂正符号

セル・オートマトンを誤り訂正符号の設計に応用した例として、D. Roy Chowdhury、S. Basu、I. Sen Gupta、P. Pal Chaudhuri の論文 "Design of CAECC - Cellular Automata Based Error Correcting Code" がある。この論文ではセル・オートマトンを使って SEC-DED符号(1ビット誤り訂正-2ビット誤り検出符号)を構築する新たな手法が定義されており、その符号の高速ハードウェアデコーダも報告されている。

具体例

セル・オートマトンが登場するフィクション

参考文献

  • 『自己増殖オートマトンの理論』- フォン・ノイマン著 岩波書店
  • 『アインシュタインの部屋』 - エド・レジス著 工作社
  • 『コンピューターレクリエーションI 遊びの発想』 - A.K.デュードニー著 別冊サイエンス32
  • 『哲学者クロサキと工学者アイハラの神はカオスに宿りたもう』 - 合原 一幸、 黒崎 政男 共著
  • "History of Cellular Automata" from Stephen Wolfram's A New Kind of Science
  • Cellular automaton FAQ from the newsgroup comp.theory.cell-automata
  • Neighbourhood survey 三角格子や大きな近傍のセル・オートマトンなどを論じている
  • von Neumann, John, 1966, The Theory of Self-reproducing Automata, A. Burks, ed., Univ. of Illinois Press, Urbana, IL.
  • Wolfram, Stephen, 1985, Cryptography with Cellular Automata, CRYPTO'85.
  • Cosma Shalizi's Cellular Automata Notebook 書誌情報が豊富
  • Wolfram's papers on CAs
  • A.M. Turing. 1952. The Chemical Basis of Morphogenesis. Phil. Trans. Royal Society, vol. B237, pp. 37 - 72. (proposes reaction-diffusion, a type of continuous automaton).
  • Jim Giles. 2002. What kind of science is this? Nature 417, 216 - 218. (discusses the court order that suppressed publication of the rule 110 proof).
  • Zuse´s publications on CA-based physics (1967, 1969, 1970), with comments by Juergen Schmidhuber
  • Frish U., Hasslacher B., and Pommeau Y. Lattice gas method for partial differential equations. Phys. Rev. Lett., 56(1505), 1986.
  • Peak, West, Messinger, Mott (2004) "Evidence for complex, collective dynamics and emergent, distributed computation in plants". Proceedings of the National Institute of Science of the USA 101 (4), 918-922

関連項目

外部リンク

Template:Link GA