セルオートマトン #1 イントロダクション

こんばんは．今回はセルオートマトンについて．
セルオートマトンで有名なのは，ライフゲーム(Game of Life)ですが，今回は違います．

1次元セルオートマトン(Cellular automaton)

1次元セルオートマトンは，最もシンプルなセルオートマトンです．
セルは1次元に並んでいて，あるセルに2つのセルが隣接しています．
また，セルの種類は“0”，“1”の2つのみです．ここでは0を□，1を■とします．

□■□■■■□□
例えばある時刻tでは，こんな感じ．

そして，

a_k^t+1=f(a_k-1^t, a_k^t, a_k+1^t)

という式により，セルを更新します．
a_k^tは時刻tにおける，k番目のセルの状態であり，
a_k-1^tはその左隣，
a_k+1^tはその右隣
を表します．
つまり，時刻t+1(次の時刻)のセルの状態は，時刻t(現在)のセルとその両脇のセルの状態によって決まるわけです．

更新に使うfは例えば下のようなものです．

時刻tでの状態 (ak-1t, akt, ak+1t)	(1, 1, 1)	(1, 1, 0)	(1, 0, 1)	(1, 0, 0)	(0, 1, 1)	(0, 1, 0)	(0, 0, 1)	(0, 0, 0)
時刻t+1での状態 akt+1=f(ak-1t, akt, ak+1t)	0	0	0	1	1	1	1	0

同じですが以下のようにも書けます．

時刻tでの状態(左，中央，右)	■■■	■■□	■□■	■□□	□■■	□■□	□□■	□□□
時刻t+1での状態(中央)	□	□	□	■	■	■	■	□

このような“ルール”を各セルに適用します．

例:
□■□■■■□□
とりあえず，両端は考えない事にします．その内側のみを更新します．
□■□ → ■
■□■ → □
□■■ → ■
■■■ → □
■■□ → □
■□□ → ■
なので，
□■□■□□■□
となります．

これを繰り返していくだけです．

この“ルール”の数は，
左，中央，右の3セルが作る状態数=8，
1つの状態に対する，次のセルの状態数=2，
であるので，
2⁸=256通りとなります．

具体的には，

時刻tでの状態	■■■	■■□	■□■	■□□	□■■	□■□	□□■	□□□
ルール0	□	□	□	□	□	□	□	□
ルール1	□	□	□	□	□	□	□	■
ルール2	□	□	□	□	□	□	■	□
ルール3	□	□	□	□	□	□	■	■
…
ルール252	■	■	■	■	■	■	□	□
ルール253	■	■	■	■	■	■	□	■
ルール254	■	■	■	■	■	■	■	□
ルール255	■	■	■	■	■	■	■	■

□=0，■=1なので，“ルール30”とかいったら，30を2進数(=00011110)に直せばいいわけです．

以上で，このモデルの説明は終わりです．

さてさて，セルオートマトンは，その振る舞いから，以下の4クラスに分類されます．

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

クラス1，2は単純過ぎ(簡単に予測できる)，クラス3はカオス過ぎ，クラス4が丁度良い，つまり，現実世界で起こる現象に近いのではないか，と考えられたみたいです．

というわけで，全ルールを(出来れば)紹介していきます．