4点を参照するセルオートマトン(CA)についてちょっと調べている.
4点を参照する1次元セルオートマトン
等価なウルフラムコード
ランダムな初期条件を与えたとき
ランダムな初期条件を与えた時の挙動を分類したいが,ルールが多すぎて(=2^16),手作業では不可能だ.そこで,計算機にて機械的に分類することにする.
クラスの定義
Wolframは規則をクラス1からクラス4の4つのクラスに分類している.しかし,これだと大雑把すぎるので,もう少し細かく分類した次のクラス分類を用いることとする.注目するのは,ランダムな初期値を与えたときに,十分ステップが進んだ定常状態での挙動である.
- クラスA ― 初期値のすべての情報が失われ,全てのセルが同一の値を持つ.クラス1.
- クラスB ― すべてのセルが一様に定速度で移動する.クラス1.
- クラスC ― すべてのセルが周期的に振動しながら,一様に定速度で移動する.クラス2.
- クラスD ― 異なる速度での一様な移動が重なり合うような挙動をする.クラス2.
- クラスE ― 規則的なパターンがぶつかって反射し合うような挙動をする.クラス2?
- クラスF ― 一様にランダムな挙動.クラス3.
- クラスG ― 一様ではないランダムなパターンを描く.クラス3.
- クラスH ― 規則的なパターンとランダムなパターンが混在する.クラス4.
暫定でこの8つに分類することを考える.定性的であいまいな分類なのが,嫌ではある.厳密な定義はできなものか.
クラスへの分類(クラスA,B,C)
今回は,簡単に機械的に分類できるクラスA,B,Cについて調べる.初期条件はセルの数をNとすると組み合わせは2^Nあり,すべての場合について調べることは不可能だ.また,ランダムに初期条件を選ぶ試行を複数行いアンサンブルをとるのも非常に面倒である.そこで領域を大きく取ることで対応することにする.セル数は4096,時間ステップも4096.初期での1点の情報が領域を3周することになる.
分類したものがこちらのファイルになる.
U(Unknown)はクラスA,B,C以外の未分類なものである.特徴的な量は周期[ステップ],移動速度[セル/ステップ],収束までの時間[ステップ]である.クラスA,Bは周期1となる.また,移動速度はルールが左右対称でないのを補正するため,+0.5を加えている.左右対称は同じものとみなすので,絶対値をとっている.また,収束までの時間は,すべてのセルの値の和をもとに見積もっている.したがって,部分的に収束していても,収束とはみなされず,全体が定常に達したときを収束したとみなす.この値は初期値にかなり依存すると思われる.2730ステップ以降に定常になったものは,定常に達したとみなしていない.
内訳であるが,全65536のルールのうち,クラスA,B,Cそれぞれ,2513,16818,23671個であった.
クラスA
全65536のクラスAは2513個であった.
クラスAはすべての情報が失われていくので,特性量は収束までの時間しかない.これが最も短いのはルール0(ルール65535)である.いかなる入力に対しても同じ出力を返す.図はルール0である.図には256セルx256ステップのものを示す.
収束までの時間が長いのは,ルール13260(23130,42405,52275)とルール27030(38505)である.理由はよく分からないが,このルールは周期境界の場合には,それぞれ周期の半分と3分の1のステップで全て同じ値になる.すべてのセルが同じ値を取るまでは,ランダムに動いているよう見え,非常に興味深い.クラスFと分類するものの中にも,非常にながい周期でこういう風になるものが含まれている可能性がある.
残りは,以下のように時間が進むにつれて情報が消えていく.
クラスB
移動速度は0.5か1.5セル/ステップの2通りである.
非常に短い時間で収束するものもあるが,収束が遅いものもある.その差は明瞭ではないため,これらを分けることは難しい.収束が長いものは,一点の情報が他とは異なる方向に伝わっていき,ぶつかって壊れるというような動きをする.この動きは初期値に強く依存するので,収束の長さの違いは初期値によるものと思われる.
クラスC
もっとも周期のながかったのは,ルール27022の1260ステップ.長すぎて本当かな?と思うが,複数の周期の振動が存在すると,ここまで大きくなるのだろう.
興味深いのは周期が2^Nになっているもの.フラクタル図形の一つであるシェルピンスキーのギャスケットが組み合わさった模様を描く.Nがどの数字を取るのかは初期値によるものと思われる.
収束の過程は,クラスA,Bと同様に次の2通りがある.一つは,左のようにパターンがいくつかできるが,ステップが進むにつれて,安定な1つのパターンになるという場合.もう一つは,右のように一部の情報が,異なる方向で伝わっていくが,ぶつかって壊れるというものである.
今後
下のようなクラスDに分類するものは,見た目では簡単に分かるのだが,機械的に分類するとなると,どうやっていいかちょっとよく分からない.クラスDかどうかを判断できるアルゴリズムを考えたい.