だいぶ前にふと立ち寄った大学生協で買ったものの、ろくに読んでなかったセルオートマトンの本を読みつつ、遊んでみた。 今回遊んだセルオートマトンは初等セルオートマトンという単純なものだが、離散数学の面白さに少しふれられた気がする。
この初等セルオートマトンの各ルールやパラメータを気軽に試せるデモを作成して以下に公開した*1。READMEから主なRuleへのリンクを張っている。 github.com
ちなみに、初等セルオートマトンとはなんぞやという話を簡単にしておく。自分の理解は以下。
- 一次元セルオートマトンで、セルの集合は1次元格子状に配置する。
- セルの状態は0と1のみの最も単純なものを対象とし、0は白、1は黒で表現する。*2
- セルの状態は離散的な時間間隔で変化し、セルの状態変化は同時にすべてのセルに対して行われる。*3
- i番目のセルの時刻tにおける状態は、時刻t-1における、i-1番目のセルの状態とi番目のセルの状態とi+1番目の状態によって決定的に決まる。*4*5
- セルの状態遷移関数は、決定的なものであれば256種類しかなく、Rule0からRule255として区別されている。
- 状態遷移関数の定義次第では、規則性をもったり(Rule 1)、完全にランダム(Rule 30)になったり、周期性を持ったり収束したり(Rule 184)変化する。
- 完全にランダムな状態変化*6を簡単に生成できるので、暗号などへの応用も研究されているらしい。*7
- 基本的にはセルの数を有限と仮定する場合は境界条件に留意する必要がある。周期境界条件を用いれば可逆性や周期性が確認できる*8。
それから、2次元セルオートマトンということで、ライフゲームも作ってみた。これも別に簡単なのに動かしたらいきなりそれっぽく動いて面白かった。
動き方は以下。
- ムーア近傍8セルのうち、3セルが生きていれば、次は生きる。
- セルが生きていて、ムーア近傍8セルのうち、2セルが生きているとき、次は生きる。
- 上記以外のセルは死ぬ。
