セルオートマトンと複雑系

Complex Systems Created by Cellular Automata

(English here)




トップページ

ギャラリー

セルオートマトンて何?

セルオートマトンの歴史

複雑系て何?

人工生命て何?

リンク集

アイコンの説明:

  1. [new] : 新情報
  2. [good] : お勧め
  3. [demo] : デモ

セルオートマトンて何?

まず例として最も単純なセルオートマトンを紹介することにします。今、ある帯状の図形を長さ方向にN個に等分割し、分割された各々の図形をセルと呼ぶことにします。それらのセルについて、一方の端からセル1、セル2...セルNというように番号をふっていき、それぞれのセルが状態0または1をとるとします。(図1)

0110001...0

図1:0または1の状態を持つ1次元セル空間


それぞれのセルは1離散時刻単位毎に状態が更新されます。この更新は空間全体で同時に行われます。更新後もそれぞれのセルは状態0または1をとりますが、どちらになるかは1つ前の離散時刻における自分自身とまわりのセルの状態によって決定されます。すなわち、k番目のセルが時刻t+1に0または1になるかは、時刻tでのk−1、kおよびk+1番目のセルの状態によって決定されます。これを式で書くと

    akt+1 = f(ak-1t,akt,ak+1t)

と表現できます。ただし、aktは時刻tにおけるk番目のセルの状態です。fはセルの時間発展のルールを表わす関数で、ak-1t、akt、ak+1tの3つの変数がそれぞれ0または1の2つの状態を取り得ることから8種類の入力パターンに対して関数出力値を定義する、すなわち8つの写像を定義する必要があります。これらの8つの写像を1まとめにしたものをルールと呼び、各々の入力パターンはエントリーと呼ばれます。ルール自体は上記のように局所的ですが、全空間において同じルールが適用されます。ただし両端のセル0とセルNは両隣りのうち一つが欠けているので少し工夫が必要です。例えばセル0の左がセルNになるように空間を周期的してしまえばルールがそのまま使えます(これは周期的境界条件と呼ばれています)。また、架空のセル0とセルN+1を定義し、それらを常に0(または常に1)にする方法も考えられます。このように空間全体に対し一様にルールが適用されるわけですが、これは時間についても同様で同じルールが何度も何度も適用されます。こんな単純なもので複雑な現象が研究できるるのかと疑いたくなるかもしれません。下の図2 は、f(1,0,0)=1およびf(0,0,1)=1以外はすべて0状態を出力するようなルールを適用した時に得られるセルオートマトンの時間発展です。上に行くにに従って時間が経過するようにグラフが書いてあります。面白いことに1個の状態1のセル(黒点)の初期状態から、有名なフラクタル図形であるシルビンスキーのガスケットができあがります。このようにセルオートマトンは複雑な図形も簡単なルールで作ってしまう、なかなか奥が深いものなのです。


図2:セルオートマトンで作ったフラクタル図形

さてここまでは、最も単純なセルオートマトンの例を紹介してきました。もうお分かりでしょうが、セルオートマトンは目的にあわせてもっともっと複雑することができます。まずセル空間が多次元のセルオートマトンを定義できます。原理的にはn次元のセルオートマトンが可能ですが、現実的には3次元までで実際研究されているのも3次元までです。また上の例では、状態数は0か1の2状態を考えましたが、これにも状態が整数であれば特に制限はありません。また、ルール関数の入力になる周りのセルを自分自身も含めてネイバーと呼んでいます。上の場合は自分自身も含めて3つのネイバーが入力に使われましたが、k-2番目とk+2番目のセルもネイバーに含めた5ネイバーでルールを定義することもできますし、より離れたセルをネイバーに使うことも可能です。2次元の場合には自分自身と前後左右のセルで5ネイバー(フォンノイマン・ネイバーフッド)や、斜め隣の4つのセルも入れる9ネイバー(ムーア・ネイバーフッド)が一般的に用いられています。最もよく知られているセルオートマトン、ライフゲーム(Game of Life: GOL)は2次元、2状態数、9ネイバー構造を用いています。(GOLのデモはこちら。)因みにこの場合、エントリー数が29=512個存在し、全ルール数は2512と膨大な数になってしまい、これを全部調べるというのはちょっと困難です。しかしながら、セルオートマトンにはルールと実行結果を結びつけるための決定的な理論はなく、現実的にはやはり実行してみるまでは実行結果が分かりません。それではこの数学的には厄介な代物ですが、一体何のために考え出されたのでしょうか?それには次節のセルオートマトンの歴史を読んで下さい。

ある数学的道具を使っているとその枠組みでは満足できなくなり自分で枠組みを拡張する人が必ずいます。セルオートマトンもそのようにして様々な拡張版が考案されました。以下にその例を挙げてみます。
  1. 状態を整数だけでなく、実数にまで拡張する。
  2. 適用するルールをセル空間の位置や時間によって変化させる。
  3. 状態の更新を空間全体で同時に行わず、非同期で行う。
  4. ルールの写像が一意的ではなく、確率的に出力を決定する。
狭義ではこれらはセルオートマトンではありません。私自身はセルオートマトンの本質は離散空間、離散時間および局所的ルールであると考えています。よってこれらの拡張版もある種のセルオートマトンと言っていいと思います。
[CA] [CA] [CA] [CA]

Last Modified on 29, January, 2004