1次元セルオートマトン

オートマトンというは自動装置という意味らしいです。 セルオートマトンというのは、セルを用いた自動装置という意味でしょうか。 今回は、1次元のセルオートマトンのRule90という規則から シェルピンスキーのギャスケットとよばれる図形を作成します。

シェルピンスキーのギャスケット

セルの状態と表示

セルのとり得る状態は0か1の二種類とします。 セルは次のように直線状に並んでいるとします。
0001101001011000
このままだと図形として認識しにくいので、 実際のセルの状態表示は「0 ならば □」「1 ならば ■」で置き換えて表示します。

0001101001011000
     ↓
□□□■■□■□□■□■■□□□

Rule90

Rule90というのは、旧世代のセルから新世代のセルを生成する規則です。

新世代のn番目のセルが1となるのは、旧世代のn番目のセルの両隣の「状態1のセル」の個数が1のときです。 その他のケースは0とします。

また便宜上、「左端のセルの左」と「右端のセルの右」に状態0のセルがあるとみなします。

例.

00100 → 01010 → 10001 → 01010 → 10001 → ...

今回作成するシェルピンスキーのギャスケットは

00000000000000100000000000000

というような中央に1つだけ状態1のセルがある状態を最初の世代として、 この世代にRule90を適用して、それらを縦に並べて構成します。

□□□□□□□□■□□□□□□□□
↓(Rule90)
□□□□□□□■□■□□□□□□□
↓(Rule90)
□□□□□□■□□□■□□□□□□
↓(Rule90)
□□□□□■□■□■□■□□□□□

Maximaのプログラム例

/* 1行のセルの数が 30+1+30=61 の中央が 1 で他が 0 の list を用意 */
N:30;
list1:makelist(0,i,1,N)$ 
list2:endcons(1,list1)$
list:append(list2,list1)$
/* 0 と 1 からなるリストを □ と ■ でおきかえた文字列を得る.*/
GetString(list):=
block(
    [st:""],
    for a in list do (
        if oddp(a) then st :sconcat(st,"□")
        else st :sconcat(st,"■")),
    st
);
/* n番目のセルの両隣の1であるセルをカウント.*/
Count(list,n):=
block(
  [sum:0],
  if n>=2 and list[n-1] = 1 then sum:sum+1,
  if n < length(list) and list[n+1] = 1 then sum:sum+1,
  sum
);
/* 旧世代のセル(list)から新世代のセル(list1)を返す. */
Rule90(list):=
block(
    [list1:[]],
    for i:1 thru length(list) do (
       if Count(list,i) = 1 then list1:endcons(1,list1)
        else list1:endcons(0,list1)
    ),
    list1
);
/* セルの表示とRule90による更新をくりかえす. */
for i:1 thru N do(
    print(GetString(list)),
    list:Rule90(list)
);