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