セルオートマトンの分類

前回の続きでセルオートマトンについて書いていきます。

otepipi.hatenablog.com

今回はセルオートマトンの分類についてになります。 以下書籍を参考にしています。セルオートマトンに関する和書は数少ないですが、その中でも特に詳細に記述されている用に思います。

セルオートマトン

セルオートマトンの分類

Wolfram（Mathematicaの開発者として有名ですがセルオートマトンでも多大な貢献をしています）はセルオートマトンの時間発展の挙動を以下4種類のクラスに分類しました。 * クラスⅠ * クラスⅡ * クラスⅢ * クラスⅣ

クラスⅠのオートマトン

　クラスⅠのオートマトンはどのような初期値をとったとしても、時間発展の過程で必ずある固定状態に収束するものを指します。 例として規則249のオートマトンを考えます。

現在の状態	中央のセルの次の状態
111	1
110	1
101	1
100	1
011	1
010	0
001	0
000	1

このオートマトンをJuliaで実装して実行してみます。 初期値はランダムにします。

using LinearAlgebra
using Plots
using Random


RULE=249;
SPACE_SIZE=100;
TIME_STEP=30;

global state = zeros(SPACE_SIZE);
global next_state = zeros(SPACE_SIZE);
global state_time = zeros(TIME_STEP,SPACE_SIZE);

###　初期条件 ランダムな1と0の数列
state = bitrand(SPACE_SIZE)'

#stateの評価
for time = 1:TIME_STEP

for i = 1:SPACE_SIZE
    l = state[if i > 1 i-1 else SPACE_SIZE end]
    c = state[i]
    r = state[i % SPACE_SIZE + 1]
    neighbor_cell_code = Int(2^2*l + 2^1*c + 2^0*r) 

    if RULE >> neighbor_cell_code & 1 > 0
        next_state[i] = 1;
    else
        next_state[i] = 0;
    end
end
state_time[time,:] = state[:]
state[:] = next_state[:]
end

## 描画
heatmap(state_time, yflip = true, c = :heat, legend = false,
        ylabel="time step")

結果、初期値によらず時間発展の過程ですべて１になります。 これがクラスⅠの性質です。

規則249

規則249 別の初期値で

クラスⅡ

クラスⅡのセルオートマトンの性質は周期的な振る舞いです。 例として規則150の振る舞いを確認してみます。

現在の状態	中央のセルの次の状態
111	1
110	0
101	0
100	1
011	0
010	1
001	1
000	0

これを実装して実行すると以下のように繰り返し構造が現れます。これがタイプⅡの特徴です。

規則150 セル数17 80ステップ

また、タイプⅡの中には特定のデータの並びを保存し、他を無効とするデジタルフィルタの役割を果たすものもあります。 例として規則4の振る舞いをみてみます

現在の状態	中央のセルの次の状態
111	0
110	0
101	0
100	0
011	0
010	1
001	0
000	0

上表のように、規則4は010の並びが存在するときのみ1となり、それを保存する働きをします。

010の部分のみ保存されることがわかります。

クラスⅢ

クラスⅢのセルオートマトンはランダム性の強い構造を形成します。この構造は強い初期値依存性を示し、カオス的な挙動を示します。 例として規則126を挙げます。

現在の状態	中央のセルの次の状態
111	0
110	1
101	1
100	1
011	1
010	1
001	1
000	0

これは以下のようにランダムで予測できない構造を示します。

規則126

クラスⅣ

クラスⅣは厳密な定義のないもので、強いて言うなら局所的に見出される構造が互いに相互作用しているような挙動を示すようです。 例として規則110を紹介します。

現在の状態	中央のセルの次の状態
111	0
110	1
101	1
100	0
011	1
010	1
001	1
000	0

これを描画したものが以下になります。正直よくわかりませんが、局所的な構造がセル内を移動しているような様子が伺えます。これがタイプⅣの特徴のようです。このタイプⅣのセルオートマトンは計算万能性を持つ可能性があり。重要度が高いそうです。

以上、４つの分類を簡単に紹介しました。 今回はここまでにしたいと思います。