仮想計算機構

IT業界と無縁な派遣社員のブログ

Tempesti loop:自己複製しながら文字を描くセルオートマトン

はじめに

自己複製するオートマトンには様々なパターンがあり、Wikipediaには簡易的な比較表があります。
Langton's loops - Wikipedia
比較表のうち、Langton's loopとByl's loopは実装しました。


今回はTempesti loopと呼ばれるセルオートマトンを実装します。といってもプログラムの中身は以前作ったものとそれほど変わりありませんが。

Tempesti loop

Tempesti loop は1995年にG.Tempestiが発表した自己複製するセルオートマトンです。詳しい内容については以下のリンクから読むことができます。
http://fab.cba.mit.edu/classes/MAS.865/replication/Tempesti.pdf

主な特徴は以下の通りです。

  • 自己複製しながら別のタスクを実行することができる。
  • タスク実行に必要なデータはループ上をぐるぐる周っている。
  • オートマトンの隅にゲートセルがあり、ループの複製が終わるとセルがOPENからCLOSED状態になる。
  • 4つの構築アームが4方向へ伸びていく。アームの伸びた先にすでにコピーされたループがあるときはアームを引っ込める*1
  • なんらかの指示を受けてアームが伸びる、というわけではなく指示がない限りアームは伸び続ける。
  • アームへ指示を送るときは、メッセンジャーをアームの先端へ送る必要がある。そのため、メッセンジャーはアームより早く動くようになっている。
  • 複製手順
    • 1.まずループの内側部分を作る。これが複製の際の土台になる。
    • 2.次にループ上を周回するデータが複製され、コピーされたデータが新しいループへ送信される。
    • 3.データが土台部分を包み込み、ループ全体が複製されたときアームは引っ込み*2、複製が完了する。

ラングトンのループとの相違点は以下のとおりです。

  • von Neumann近傍ではなくMoore近傍を使う ( Moore neighborhood - Wikipedia )
  • 遷移規則の記述にrotate4を使わない。
  • データを包み込むための外側のセルがない。
  • データは複製が完了した後もループ上を周回し続ける。
  • セル空間の淵にきたときにクラッシュ*3しない。これはアームが淵にあたると、アームが引っ込む*4ため。
  • 4方向へきれいに増殖していく(ラングトンのループは4方向へ増えますが、対称性には欠けます)。

Tempesti loop の概要は以上です。さっそく実装してみます。

プログラム

HTML/JavaScriptでプログラムを作成しました。

<html>
    <body>
        <script type="text/javascript" src="tempesti_rule.js"></script>
        <script type="text/javascript" src="tempesti_loops.js"></script>
    </body>
</html>

遷移規則については今までは下記サイトの該当ファイルからコピペしたものをそのまま使っていました。今回はそう簡単ではありません。
GitHub - GollyGang/ruletablerepository: Previously at https://code.google.com/p/ruletablerepository
というのも、Tempesti.tableというファイルには状態を表現する0から9までの数字以外に a や b といった記号を含むルールが存在するからです。そのため、ルールをコピペしてきてもプログラムはうまく動きません。この問題は以下の記事で解決しているので参考にしていただければと思います。
圧縮されたルールテーブルから元のルールテーブルを復元する - 仮想計算機構
上述の記事で作成したルールをコピーして以下のように貼り付けます。

const tempesti_rule_str = `2500051115 
2600051115 
...
2005511505
7002511502
2007511707`

最後にメインのプログラムです。tempesti loop の初期配置は論文の図6から拝借しました。Byl's loop などと比べると初期配置に要するセルは多めです。

const WIDTH = 630;
const HEIGHT = 340;

const canvas = document.createElement('canvas');
canvas.width = WIDTH;
canvas.height = HEIGHT;

const context = canvas.getContext('2d');

document.body.appendChild(canvas);

const CELL_SIZE = 3;
const N_ROW = Math.round(HEIGHT / CELL_SIZE);
const N_COL = Math.round(WIDTH / CELL_SIZE);

const tempesti_loops = [
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0],
    [0, 2, 6, 8, 6, 6, 6, 6, 6, 6, 6, 7, 6, 6, 5, 5, 5, 5, 5, 5, 2, 0],
    [1, 9, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 5, 0],
    [0, 6, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 5, 0],
    [0, 6, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 5, 0],
    [0, 6, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 5, 0],
    [0, 8, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 5, 0],
    [0, 6, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 5, 0],
    [0, 6, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 5, 0],
    [0, 6, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 5, 0],
    [0, 6, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 5, 0],
    [0, 8, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 5, 0],
    [0, 6, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 5, 0],
    [0, 6, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 5, 0],
    [0, 7, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 5, 0],
    [0, 6, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 5, 0],
    [0, 6, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 5, 0],
    [0, 7, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 5, 0],
    [0, 6, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 5, 0],
    [0, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 7, 1],
    [0, 2, 6, 9, 6, 6, 7, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 5, 7, 2, 0],
    [0 ,0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
];

const state2color = {"0":"black", "1":"blue", "2":"red", "3":"green",
                     "4":"yellow", "5":"magenta", "6":"white", "7":"cyan", "8":"brown","9":"gray"};

class Tempesti{
    constructor(){
        this.init_field();
        this.load_rule();
    }
    init_field(){
        // fieldの初期化
        this.field = new Array(N_ROW);
        for(let i=0;i<N_ROW;i++){
            this.field[i] = new Array(N_COL).fill(0);
        }
        // Tempesti Loopを配置する
        let offset_y = Math.round((N_ROW - tempesti_loops.length) / 2);
        let offset_x = Math.round((N_COL - tempesti_loops[0].length) / 2);

        for(let y=0;y<tempesti_loops.length;y++){
            for(let x=0;x<tempesti_loops[y].length;x++){
                this.field[y + offset_y][x + offset_x - 10] = tempesti_loops[y][x];
            }
        }
    }
    load_rule(){
       this.rules = {};
       let l = tempesti_rule_str.split("\n");
       for(let i=0;i<l.length;i++){
           let neighbor = l[i].slice(0,9);
           let next_c = l[i].charAt(9);
           //C,N,NE,E,SE,S,SW,W,NW,C
           let [c,n,ne,e,se,s,sw,w,nw] = Array.from(neighbor);
           this.rules[c+n+ne+e+se+s+sw+w+nw] = next_c;
       }
    }
    update(){
        let next_field = new Array(N_ROW);
        for(let i=0;i<N_ROW;i++){
            next_field[i] = new Array(N_COL).fill(0);
        }
        for(let y=1;y<N_ROW-1;y++){
            for(let x=1;x<N_COL-1;x++){
                let c = "" + this.field[y][x];
                let n = "" + this.field[y - 1][x];
                let ne = "" + this.field[y - 1][x+1];
                let e = "" + this.field[y][x + 1];
                let se = "" + this.field[y + 1][x + 1];
                let s = "" + this.field[y + 1][x];
                let sw = "" + this.field[y + 1][x - 1];
                let w = "" + this.field[y][x - 1];
                let nw = "" + this.field[y - 1][x - 1];
                if((c+n+ne+e+se+s+sw+w+nw) in this.rules){
                    next_field[y][x] = Number(this.rules[c+n+ne+e+se+s+sw+w+nw]);
                }else{
                    next_field[y][x] = this.field[y][x];
                }
            }
        }
        this.field = next_field;
    }
    render(ctx){
        for(let y=0;y<N_ROW;y++){
            for(let x=0;x<N_COL;x++){
                ctx.beginPath();
                ctx.fillStyle = state2color[this.field[y][x]];
                ctx.rect(x*CELL_SIZE,y*CELL_SIZE,CELL_SIZE,CELL_SIZE);
                ctx.fill();
            }
        }
    }
}

var tempesti = new Tempesti();
count = 0;
function loop(timestamp) {
  context.clearRect(0, 0, WIDTH, HEIGHT);
  tempesti.render(context);
  tempesti.update();
  context.fillStyle = "white";
  context.font = "20px sans-serif";
  context.fillText("time : " + count, 10, 30);
  count++;
  window.requestAnimationFrame((ts) => loop(ts));
}

window.requestAnimationFrame((ts) => loop(ts));

実行結果


先ほど Tempesti loop の主な特徴を挙げましたが、この1分弱の動画からでも特徴のいくつかは把握できると思います。

  • 自己複製以外のタスクを行っている(LSL*5と描いている)
  • 淵にぶつかってもアームを引っ込めるため、ループ自体がクラッシュしない
  • 4方向に等しく増えていっている
  • 内側の複製が終わったあとにデータが複製される
  • 複製が終わってもデータがループを周回している
  • アームの伸びるスピードより速いセル(メッセンジャー)がある
  • かわいい

今後は、もう少し複雑な文字が描けるが試してみたいと思います。

追記(2020/07/05)

下記サイトからも見れるようになりました。
http://riverta.net/gallery/ca/index.html

*1:かわいい

*2:かわいい

*3:クラッシュする様子は→https://www.youtube.com/watch?v=y_gk1_5LibM

*4:かわいい

*5:Logic Systems Laboratory の頭文字らしい。海外の人ってこういうの好きですよね