セルオートマトン:1次元:Rule 30の話

セルオートマトンという研究分野があります.n次元内でのセルという単位を設定します.セルには事前に何種類かの値(状態)を設定します.時点t においてのセルの状態と隣接(近傍)のセル状態によって、何らかの状態遷移式を通して,次時点(t+1)の各セルの状態が決定されると設定しちゃいます.

1次元セルオートマトンの場合,セルの展開は直線であり,1次元配列xにすると
要素数 i の場合 近傍セルはx{i-1}と x{i+1}になるので

tにおける,x{i-1}とx{i}とx{i+1}の状態によってt+1のx{i}の状態が決定するということになります.

状態を0と1の2つと設定した場合,x{i-1}とx{i}とx{i+1}がとりうるのは

左   中     右

0 0 0

0 0 1

0 1 0

0 1 1

1 0 0

1 0 1

1 1 0

1 1 1


に8パターンになります

その8パターンにおいて,真ん中のセルx{i}が0と1どちらをとりうるかを考えると
2の8乗になるので256通りあることになります
それらは ウルフラム・コードRule0からRule255と呼ばれ,既に研究しつくされています

まずは一番有名なRule 30 について

x{i-1} x{i} x{i+1}     t+1のx{i}
0 0 0 ➡ 0

0 0 1 ➡ 1

0 1 0 ➡ 1

0 1 1 ➡ 1

1 0 0 ➡ 1

1 0 1 ➡ 0

1 1 0 ➡ 0

1 1 1 ➡ 0


x{i}の次時点の値01111000を2進数から10進数に直すと30なのでRule30と呼ばれています

Rule30でいくと 仮に初期状態が





なら次の状態は(両終端のその先は0とします)







こうなります,例えばtで左から2番目のセルがt+1で1になっているのは
0 0 1➡ 1の遷移ルールに従うからです 
さて,このようにしてtをドンドンすすめていって,値がどう遷移していくかを
仮に,蓄積してビジュアライゼーションすると何が起こるかを見てみましょう

今,配列数を200要素として,次時点の値を格納する配列も同数用意し
Rule 30をそのまま select文にぶち込んでしまって,tをオブザベーション数と考えて
100回ほどループさせてみます

data wk1;
array col{200}  (200*0);
array ncol{200}  (200*0);

col{100}=1;

do obs = 1 to 100;
do i = 1 to 200;
if obs = 1 then do;
ncol{i}=col{i} ;
end;
else do;
if i=1 then pattern=cats(0, col{i},col{i+1});
if (1+1)<=i<=(200-1) then  pattern=cats(col{i-1},col{i},col{i+1});
if i=200 then pattern=cats(col{i-1}, col{i},0);
/*rule*/
select(pattern);
  when("000") ncol{i} =0;
  when("001") ncol{i} =1;
  when("010") ncol{i} =1;
  when("011") ncol{i} =1;
  when("100") ncol{i} =1;
  when("101") ncol{i} =0;
  when("110") ncol{i} =0;
  when("111") ncol{i} =0;
end;
end;
end;
  output;
  do i = 1 to 200;
    col{i}=ncol{i} ;
  end;
end;

keep ncol:;
run;

結果にういて,0を白色,1を黒色として,SAS RWI(Report Writing Interface)で描画してみます(先のコードと同じステップでもいいですが,見やすさのためデータステップを分けました)

data _null_;
set wk1 end=eof;
array AR ncol:;
if _N_=1 then do;
  dcl odsout ob();
ob.table_start();
end;
ob.row_start();
do over AR;
if AR=1 then do; background="black";color="black";end;
else if  AR=0 then do; background="white";color="white";end;
text=catx(" "," color=",color," height=0.01 width=0.01  vjust=center background=",background);
ob.format_cell(data:AR,style_attr:text);
call missing(of background color);
end;
ob.row_end();
if eof then do;
ob.table_end();
end;
run;














↑がSASの出力ですが,このパターンはイモガイの一種の紋様と類似します.
これは貝殻に格子状に存在する色素細胞が隣接細胞に活性阻害の影響を与えるため,天然のセルオートマトンとして働いているからという原理のようです














画像と,紋様とRule30については以下より参照
(Coombs, Stephen (February 15, 2009), The Geometry and Pigmentation of Seashells
https://www.maths.nottingham.ac.uk/plp/pmzsc/pdfs/Seashells09.pdf


こんな風に,セルの相互関係と単位時間での状態遷移を考えたセルオートマトン,原理はシンプルでプログラムでの実装も(1次元なら特に)平易ですが,
Rule 30は面白いことに,ある生物学的過程を綺麗にシミュレートできました

次もこの面白いセルオートマトンのことをもっと紹介していこうかなと思います~