セルオートマトン

セルオートマトン
2011/4/25
セルオートマトンの仕組み
• セル(通常は正方形)で構成された空間の状
態を更新していく 更新は全面的に行われる
• 時間は離散的であり、t-1の状態からtの状態
を算出する
• あるセルの時間tの状態の算出に関与するセ
ルをネイバーという
• もっとも「楽しい」セルオートマトンはライフ
ゲームとして知られる
ライフゲーム
・1970 conwayにより提唱
ムーアネイバーフッド:9
□□□
□□□
□□□
・ルール:近傍の生存セルが2,3なら中央のセル
は生き残る
近傍の生存セルが3なら中央のセルは誕生す
る
23/3
ライフゲーム
• 初期パターンからどのような変化をたどるか
予想つかない
→カオス・複雑系との関連?
• 増え続けるパターンはあるか?
→グライダー・シュポシュポの発見
• 情報理論との関連は?
→完全チューリングマシンであることが証
明される
カオス・複雑系
・ローレンツ
• アトランダムな中にもパターンがあるらしい
• バタフライ効果
チューリングマシン
•
•
•
•
決定問題
計算可能性
チューリングマシン
万能チューリングマシン
→すべての計算機械と原理的に同じ能力を持
つ
一般のセルオートマトン
・次元
・フィールド
・状態数
・ネイバー
LOG2 理論的対象は1
無限、辺での処理、メビウスの輪
2またはそれ以上
次元によってことなるが、2次元の
場合5または9
・変換ルール 整数・合計数のほか実数、ランダム
の場合が研究されている
セルオートマトンの歴史
• von Neumann
機械またはオートマトンが自分の複製をつく
れるか?Ulamによるセルの示唆
• 1952年 複製に成功・万能チューリングマシ
ンを構成できることを証明
• 1970 ConwayがGOLを提案
• 1982 GOLが万能チューリングマシンであるこ
とが証明
一次元セルオートマトン
• 1980 Wolfram (Mathematicaで有名)
一次元セルオートマトンの研究にてクラス1~4を発
見
クラス1:セル空間がすべて同じ状態のセルに覆われてしまい、変
化しなくなる
http://www001.upp.so-net.ne.jp/suzudo/class1.gif
クラス2:セルの時間発展が局所化され、周期的または定常的にな
る
http://www001.upp.so-net.ne.jp/suzudo/class2.gif
クラス3:セル全体がランダムな時間発展をする(カオス)
http://www001.upp.so-net.ne.jp/suzudo/class3.gif
クラス4:セルの時間発展は複雑で、局所化されている。また長い過
渡状態を持つ
http://www001.upp.so-net.ne.jp/suzudo/class4.gif
セルオートマトンと相転移
Langton
・物質の相転移との関係
クラス1、2からクラス4からクラス3にいたる
過程が相転移と類似
あるセルが1である確率によりクラス3,4が
分岐
「カオスの縁」
CAと人工生命
1970~セルオートマトンによる人工生命の研究
(Langton)
・Langtonのアリ
http://upload.wikimedia.org/wikipedia/commons/a
/a3/MulticolorLangtonsAnt.gif
・Langtonのループ
・Sayamaのループ
・Sayamaのエンヴロープ
http://necsi.edu/postdocs/sayama/sdsr/
物理学との関連
• デジタル物理学
Zuze,Wolfram,Hooft,Wheleerなど
• 金属の凝固モデルなど
凝固時におけるセルラー・デンドライト遷移
• 自己組織化する量子宇宙
局所的なルールのみで宇宙が構成できるの
か?