セルオートマトン

この宇宙が、天国にいるものすごいハッカーのコンピュータで動いているセルオートマトンでできていないという証拠はない
とある研究者

今回からしばらくセルオートマトンの不思議な世界をふらついてみようと思ってます。セルオートマトンは、その名前のとおりセル（格子）から構成されたオートマトン（自動機械）です。確率とは無縁の決定論的世界ですべてはルールに厳密にしたがって動作します*1。これ以上、説明が難しいので実例を。前に、Java（2004/12/25）やPython（2008/9/14）で作ったことがあるライフゲームは、二次元セルオートマトンの一種です。

ライフゲームの各セルは、生と死（ON、OFFでもいいですけど）の2つの状態を取り、たった3つのルールにしたがって動作します。

• 生きているセルの周囲に2つまたは3つの生きているセルがあればそのセルは次の世代も生きている
• 死んでいるセルの周囲に3つの生きているセルがあればそのセルは次の世代で生き返る
• それ以外の場合には次の世代で死ぬ

たったこれだけのルールですがその振る舞いはものすごく複雑で非常に驚かされます。この格子の世界に生命の秘密が潜んでいると信じている人もいます。知らない人はぜひ動かしてみてね。参考文献の動画もおすすめ！

ライフゲームの状態とルールはものすごく単純ですが、その振る舞いは非常に複雑なので分析がすごく難しい。そんなわけでスティーブン・ウルフラム（Stephen Wolfram）という人*2がさらに単純な一次元セルオートマトンというのを考案し、詳しく分析しました。今回は、その一次元セルオートマトンを試してみようと思います。

一次元セルオートマトン

今回試すのは、二状態・三近傍・一次元セルオートマトンというもっとも簡単なものです。名前のとおり、横一列にセルが並ぶ世界で各セルは生と死の二状態を取ります。ルールもライフゲームよりずっと簡単で自分と左右の三つのセルの組み合わせから次の世代の状態が決まります。

三つのセルの組み合わせは、上の図のP0からP8の8パターン（2^3）しかありません。一方で、次の世代の状態はもっとパターンが多くなります。たとえば、上の例では、P1、P2、P3、P4のとき次の世代を「生」にし、P0、P5、P6、P7のとき次の世代を「死」とするルールになります。このルールは、「生」を1、「死」を0であらわすと00011110になるのでRule30と呼ばれています。このようなルールは、8ビットであらわせる数だけあるので全部で256種類、Rule0からRule255まであります。

でここからが面白いところ。ライフゲームの場合は、世代経過を見るには、アニメーションのように動かすしかありませんでした。ですが、一次元オートマトンの場合は、単なる線なので次世代を下方向に並べていけば時間経過を一枚の画像として見られます。実際に、第一世代を真ん中の一点のみ「生」で残りを「死」にした状態から上のRule30を繰り返し適用して次世代を下方向に重ねていくと下のような画像ができます。

一見、ランダムなノイズに見えるけどところどころきれいな三角形が見えてカオスっぽいです。次は、Rule90（01011010）を試すとこうなります。

おおおお、これは有名なフラクタル、シェルピンスキーのギャスケットではないか！本来はまったく違う作り方なのだけど一次元セルオートマトンのルールでも作れるのか・・・これはすごい。次は、Rule161を試します。

単に白黒反転したっぽいけどすこし線が太いかな？ルールを少し変えるだけで予想外の画像が出てきて面白い。

このような図を描くPythonスクリプトは下のようになります。Pythonの画像処理ライブラリのPILを使っています。

#coding:utf-8
import Image, ImageDraw, ImageFont

OFF, ON = 0, 1

def dec2bin(n):
    """10進数を2進数の01リストに変換
    下位ビットから順番に並べる"""
    bit_list = []
    for i in range(8):
        bit_list.append(n % 2)
        n /= 2
    return bit_list

def ca(width, height, rulenum):
    """1次元セルオートマトンの図を描画"""
    results = []

    # 初期状態（中央のセルだけON）
    first_row = [0] * width
    first_row[width / 2] = ON
    results.append(first_row)

    # ルールの番号から次の状態のビット列を得る
    rule = dec2bin(rulenum)

    for i in range(height - 1):
        old_row = results[-1]
        new_row = []
        for j in range(width):
            # widthの剰余を取るのは、端同士がつながっているため
            n = 4 * old_row[(j-1)%width] + 2 * old_row[j] + old_row[(j+1)%width]
            new_row.append(rule[n])
        results.append(new_row)
    return results

def render(results, width, height, filename="ca.png"):
    """セルオートマトンを描画"""
    img = Image.new("RGB", (width, height), (255,255,255))
    draw = ImageDraw.Draw(img)
    for y in range(height):
        for x in range(width):
            if results[y][x] == ON:
                draw.point((x, y), (0, 0, 0))
    img.save(filename, "PNG")

if __name__ == "__main__":
    width, height = 300, 150
    rulenum = 30
    results = ca(width, height, rulenum)
    render(results, width, height)

全256ルールをすべて描画してみた

上のスクリプトで1つずつルールを変えて画像を生成してもいいのだけれどすごく面倒なので自動化して全部描いてみました。左上の赤い数字がRule名です。

うーん、いろいろなパターンがあるのがわかりますね。すぐ死滅して真っ白になったり、繁殖しすぎて真っ黒になるルールもあります。縦や斜めに一直線もありますね。生死が反転もあります。例のカオスっぽい模様やきれいなシェルピンスキーのギャスケットもぽつぽつ見えます。出現に何か規則性はあるのかな？ルールをビット列で考えると何か見えてくるのかも。

今回は初期値を真ん中1点だけ黒にしましたがランダムにするともっといろんなパターンが出てきます。その中で物議をかもしているルールが110番です。よくわかりませんが、万能チューリングマシンであることが証明されています（ガイドツアー複雑系の世界 p.258）。

今回は、2状態・3近傍というもっとも単純なセルオートマトンでしたが、もう少し拡張していきたいと思います。次回はたぶん、ラングトンのλパラメータとカオスの縁の実験です。

参考

• ライフゲームの世界 - ライフゲームを解説した鳥肌ものの動画です！この世界は神様のライフゲームだったのか・・・と思っちゃうかも（笑）

• 参考文献が充実していてとっかかりにいい！

複雑系入門―知のフロンティアへの冒険

• 有名な一般書。2章がセルオートマトンです。冒頭の引用はここから。

人工生命―デジタル生物の創造者たち

• Stephen Wolfram: Articles on Cellular Automata - Stephen Wolframのセルオートマトン関係の論文集。原著論文も読んでみる予定。天才がどういう論文の書き方をしているのか気になる。
• Cellular Automata - このブログ記事でも全256種類のルールを全部描画しています。まねしてみました（笑）
• セル・オートマトン（Wikipedia）
• Cellular automaton (Wikipedia)
• Wolfram-style cellular automata (Python recipe) - 一次元セルオートマトンのPythonコード。ここを参考にしました。このサイトは結構マイナーなレシピもあって見てると面白いなぁ。ただ実装がエレガントすぎてすぐに理解できない（笑）

• 世界のモデルで遊ぼう - 日本語によるセルオートマトンの解説。わかりやすい。

セルオートマトン

*1:確率的セルオートマトンというのもあるみたいだけど

*2:ちなみにスティーヴン・ウルフラムは、MathematicaやWolfram Alphaを作った人と同一人物です。