セルラーオートマトン

定義

セルオートマトンとも言う。

• 有限オートマトンを規則的に(線状、格子状、蜂の巣状など)並べる。各有限オートマトンをセルと呼ぶ。
• あるセルの近傍とは、そのセルに影響を与えるセルの集合。普通は、隣接するセルの集合にする。
• セルの入力アルファベットは、近傍に含まれるセルの状態。
• ある時点のセルの状態に基づいて、すべてのセルが一斉に状態遷移を行ない、それを繰り返す。

詳しくはAlexander Schatten さんの資料、Tim Tyler さんの資料を参照。

一次元のセルラーオートマトンの動く様子が見えるページがある。二次元のもある。

Artificial Life との関係

もともとはvon Neumann が自己増殖する機械のモデルとして 研究を始めたのが最初である。自己増殖の難しさは、

• 自分と同じものを作る設計図を、自分の中に持っていなければいけない。
• 自分の中に設計図があるということは、その設計図を作るための設計図も必要になる。
• 設計図を作るための設計図も自分の中にあるので、設計図を作るための設計図を作るための設計図も必要になる。
• …と無限に続いてしまう。

というところにある。

自己増殖だけでなく、単純な規則に従う要素がたくさん集まると、全体として非常に複雑な振舞いが創発されるという現象のモデルとしてartificial lifeの研究などに広く使われている。もっとも有名なのはライフゲー ムである。