犬小屋

@justdoo1t の日記です

セルオートマトンとRule 110の話

この記事は ISer Advent Calendar 2019 の12日目として書かれました.

IS20erの犬です。昨日はあすとくんの記事でした.今日の記事ではセルオートマトンとRule 110のTuring完全性の話を扱います.

概要

この記事には,セルオートマトンや基本セルオートマトンの紹介とRule 110がTuring完全であることを示すためのTag System,Cyclic Tag System,Glider Systemについての説明が書いてあります.Rule 110がGlider Systemを模倣可能なことの説明はこの記事ではされていません.ご了承ください.

筆者はセルオートマトンに関して全くの初心者です.何か間違いがありましたらコメントか @JustDoo1t へご指摘お願いします.

セルオートマトン

セルオートマトンとは,格子状のセルと与えられた規則に基づく離散計算モデルのことを指します.ここで言う規則とは,あるセルとその周囲のセルの状態に基づいて,そのセルが次にどの状態に遷移するかを決定するような規則です.一般に,遷移はすべてのセルで同時に行われ,刻々とセル全てが変化していきます.

セルオートマトン情報科学,数学,物理学,生物学,社会科学など様々な分野で研究利用されています.情報科学や数学では計算可能性理論で扱われ,物理学や生物学では自然現象のモデル化に用いられます.単純な規則で良いモデルになることもあるようです.例えば,貝*1やトカゲ*2の模様生成がセルオートマトンで再現可能であるという論文があります.

ライフゲーム

セルオートマトンの具体的な例としては,2次元セルオートマトンの一種である『ライフゲームGame of Life)』を聞いたことがある人は多いのではないでしょうか.ライフゲームは状態数が2(0か1)で,あるセルとその8近傍のセルの状態を参照し,次の規則に基づいて状態遷移を行います.

  • 自身が1かつ,8近傍のうち2つか3つのセルが1であれば遷移後は1,そうでなければ0.
  • 自身が0かつ,8近傍のうち3マスが1であれば遷移後は1,そうでなければ0

0の状態を白,1の状態を黒として,視覚化すると次の画像のようになります.

f:id:Qoiwinski:20191209112728g:plain
状態遷移の例

単純なルールでも複雑な現象が起き,眺めているだけでも楽しいですね.

上の状態遷移の例でもわかるように,最終的に振動する(複数の状態を繰り返す)ようになるパターンや,消えずに変化しなくなるパターンがあります.他にも,消えてなくなるパターン,移動し続けるパターン,あるパターンを生成し続けるパターンも存在し,ライフゲームだけでも様々なこと*3を考えられるようです.

ライフゲームの話も面白そうで魅力的ですが,2次元のものを考えるのは大変なので次元を1つ落としたより単純な1次元セルオートマトンを考えてみましょう.

1次元セルオートマトン

一次元セルオートマトンは1列に並んだセルの上での状態遷移を考えます.与えられる規則は多くの場合,あるセルとその近傍を参照して遷移を決定します.近傍が1のとき,あるセルとその左右のセル1つずつ合わせて3つのセル,近傍が2のときはあるせると左右2つの合わせて5つのセルを参照します.

2状態2近傍の1次元セルオートマトンは5つのセルを参照して状態遷移が決定します.そのため,遷移関数の種類は2^{2^5}(4,294,967,296)通りにもなります.この膨大な数の遷移関数を個々に考えるよりは,規則を大まかに分類してそれぞれの性質を考えたくなります.

規則のクラス分け

Stephen Wolframによる以下のクラス分け*4が提唱されています.ある規則に対して,ほぼすべての初期状態から最終的にどのような状態になるかによって4つのクラスに分類されます.

  • クラス1:最終的に全て0または1になる.
  • クラス2:最終的に周期的な挙動になる.
  • クラス3:最終的にランダムな挙動となり周期性は見えない.
  • クラス4:最終的にランダムな挙動と周期的な挙動の組み合わせとなる.

各クラスの具体例は後に見ます.このクラス分けが完全かは未だ不明で,今も議論がなされています*5.具体例を見るには2近傍だとまだ複雑でつらいので,より単純な2状態1近傍1次元セルオートマトンで具体例を見ていきましょう.

基本セルオートマトン (Elementary Cellular Automata)

2状態1近傍1次元セルオートマトンは基本セルオートマトンと呼ばれます.1近傍の場合,上に述べたようにあるセルとその左右のセル1つずつ合わせて3つのセルを参照して次の状態を決定します.

つまり,遷移関数は8通りのパターン(000, 001, 010, 011, 100, 101, 110, 111)に対して中心のセルの遷移を決めています.遷移関数fにおいて,000の並びのときに中心が1に遷移するとき,f(000) = 1と書くことにします.

遷移関数の種類は2^{2^3} (256)通りであり,基本セルオートマトンの各規則には『Rule X』(Xは数字)という名前が割り振られています.Xの数字は f(111)f(110)f(101)f(100)f(011)f(010)f(001)f(000)を2進数とみなしたときの値を当てます.

色々な例

例えば,Rule 110は110を8桁2進数表示すると01101110なので,次の表のような遷移になります.

111 110 101 100 011 010 001 000
0 1 1 0 1 1 1 0

これを0を白,1を黒とみなした図にすると次のようになります.

f:id:Qoiwinski:20191209153447p:plain
Rule 110の規則

初期状態が1点の場合次図のように,

f:id:Qoiwinski:20191209192205p:plain
初期状態が1点のRule 110

初期状態がランダム(50%の確率で黒)な場合は次図のようになります.

f:id:Qoiwinski:20191209194458p:plain
初期状態がランダム(50%)なRule 110

Rule 110はクラス4に分類されます.

他にもRule 90は初期状態が1点の場合次図のように,

f:id:Qoiwinski:20191209201111p:plain
初期状態が1点のRule 90

初期状態がランダム(50%の確率で黒)な場合は次図のようになります.

f:id:Qoiwinski:20191209201738p:plain
初期状態がランダム(50%)なRule 90

Rule 90はクラス3に分類されます.

色々な例をWolframAlphaで"Rule 190"等検索することで見ることができるのでぜひ見てみましょう.私の推しはRule 30とRule 62です.

f:id:Qoiwinski:20191211053019p:plain
初期状態が1点のRule 30 かわいいね…

Rule 110はTuring完全

色々な規則の模様を見て楽しむのもいいのですが,せっかくISer Advent Calendar 2019の記事なので情報科学らしい内容を見てみましょう.Rule 110の特徴的な性質のひとつとして,Rule 110はTuring完全であることが2004年にMatthew Cook*6によって示されています.

Rule 110がTuring完全であることを示す過程は

  • Tag SystemがTuring完全なTuring機械を模倣可能なことを示し,
  • Cyclic Tag SystemTag Systemと等価であることを示し,
  • Glider SystemがCyclic Tag Systemを模倣可能なことを示し,
  • Rule 110がGlider Systemを模倣可能なことを示す.

これらの全てが示されることによってRule 110のTuring完全性が示されます.最後のRule 110がGlider Systemを模倣可能なことを示す方法は複雑で力量と時間が足りなかったので軽い紹介に留めます.

Turing完全とは

Turing完全とは万能Turing機械と同等の計算能力を持つことを指します.直感的な説明だと,一般的なプログラミング言語で計算可能な問題はTuring完全な計算モデルでも計算可能となります.よりわかりやすい説明をしている記事がたくさんあると思うのでそちらをご参照ください.

この記事では,Turing機械が何かということと,ある計算モデルがあるTuring完全な計算モデルを模倣することができるのであれば,その計算モデルをTuring完全であると言えることを理解していれば十分です.

タグシステムTag System

タグシステムとはPostにより提唱された計算モデル*7で,正整数m,記号列(左側を先頭とする),記号集合,探索テーブルによって構成されます.タグシステムはテープの先頭のアルファベットを読み,探索テーブルに従い読んだ記号に対応する記号列をテープの末尾に追加し,先頭からm文字を消去するという動作を,テープ上の記号列の長さが一定以下になるか停止記号を読むまで繰り返します.

具体的な例を見てみましょう.m=2,記号として{A, B, C, H},探索テーブルとして{A: CCBB, B: A, C: AH},初期テープがABCのタグシステムで,テープ長が2以下または停止文字Hを読み込んだときに停止するとすると,次のように動作します.

ABC (Aを読んで末尾にCCBBを追加しABを破棄)
  CCCBB (Cを読んで末尾にAHを追加しCCを破棄)
    CBBAH
      BAHAH
        HAHA (Hを読んで停止)       
タグシステムはTuring完全

m=2(削除する文字数が2つ)の場合のみ示します.2記号で十分な状態数(nとする)を持つTuring機械は万能なので,これを模倣することでタグシステムのTuring完全性を示します.

Turing機械のn個の状態に対し,次のような10n個の記号を持つタグシステムを考えます.

\{H_{p1},  H_{p0}, L_{p1}, L_{p0}, R_{p1}, R_{p0}, R_{p*},H_p, L_p, R_p, \}

 p はTuring機械の状態)

Turing機械を模倣するためには,テープの状態,ヘッダの状態,ヘッダの位置,遷移関数を模倣できる必要があります.テープの状態,ヘッダの状態とヘッダの位置は次のようなタグシステムの記号列を考えれば模倣することができます.

Turing機械のヘッドから左側の記号列を2進数としてみたときの値を T_L,ヘッドから右側の記号列をヘッドからすぐ右が最小位の2進数としてみたときの値を T_Rとし,ヘッダの状態がp,ヘッダ位置の記号が1のとき,

 \displaystyle H_{p1}H_{p0} [L_{p1}L_{p0}]^{T_L} [R_{p1}R_{p0}]^{T_R}

ヘッダ位置の記号が0のとき,

 \displaystyle H_{p0} [L_{p1}L_{p0}]^{T_L} [R_{p1}R_{p0}]^{T_R}

となるようにすればこの記号列は必要な情報をすべて持っています.これに加え,探索テーブルを次のようにすることで遷移関数を模倣することができます.

 z \in \{0, 1\},状態pで記号zを読むとき状態qに変化する.

 H_{pz}  [R_{q*} R_{q*}]^a [H_q]^b H_q [L_q L_q]^c
 L_{pz}  L_q [L_q L_q L_q]^d
 R_{pz}  R_q [R_q R_q R_q]^e
 R_{p*}  R_p R_p
 H_p  H_{p1} H_{p0}
 R_p  R_{p1} R_{p0}
 L_p  L_{p1} L_{p0}

a~eの記号は遷移の性質によって定められ,状態pで記号zを読むとき,

  • a: 1を書き込んで左に移動するなら含む
  • b: zが0なら含む
  • c: 1を書き込んで右に移動するなら含む
  • d: 右に移動するなら含む
  • e: 左に移動するなら含む

これでTuring機械を模倣することができます.d, eは,ヘッダの移動に対し, T_L, T_Rの値が倍や半分になることに対応し,a, cは倍になった T_L, T_Rに対し,1を加えるか否かに対応しています.

Turing機械の受理状態pに対し,H_{p1}, H_{p0}を停止記号とすれば停止の模倣もできます.

具体的に遷移を模倣する様子を見てみましょう.次図のようなTuring機械の遷移を考えます.

f:id:Qoiwinski:20191210210637p:plain
2記号n状態Turing機械の遷移例

遷移前のTuring機械の状態に対応するタグシステムの記号列は

 \displaystyle H_{p0} [L_{p1}L_{p0}]^3 [R_{p1}R_{p0}]^{10}

となります.上の探索テーブルに従って計算することによって遷移後の記号列が

 \displaystyle H_{p'0} [L_{p'1}L_{p'0}]^7 [R_{p'1}R_{p'0}]^5

となっているかを確認します.このTuring機械では状態pで記号0を読むと1を書き込み右に移動し状態p'となるので,探索テーブルは次のようになります.

 H_{p0}  H_{p'} H_{p'} L_{p'} L_{p'}
 L_{p0}  L_{p'} L_{p'} L_{p'} L_{p'}
 R_{p0}  R_{p'}

これに基づいて一周分計算をするとテープは

 \displaystyle H_{p'} [L_{p'} L_{p'}]^7  [R_{p'} R_{p'}]^5

となります(2つ加えられたH_{p'} の片方は最後の R_{p0}を処理するときに同時に捨てられる).
最終的にテープは

 H_{p'0} [L_{p'1}L_{p'0}]^7 [R_{p'1}R_{p'0}]^5

となり,Turing機械を模倣できています.

このようにm=2のタグシステムは記号数2のTuring機械を模倣することができ,Turing完全であることが示されました.

循環タグシステム(Cyclic Tag System

タグシステムをより簡素なモデルにしたものが循環タグシステムです.循環タグシステムはMatthew Cookにより考案され,Rule 110がTuring完全であることを示すための重要な鍵となりました.

循環タグシステムは,記号列,2つの記号{1, 0},生成規則からなります.

計算処理としては,生成規則を順々に見ていき,そのつど記号列の先頭文字を読み,1であれば見ている生成規則の記号列を末尾に追加して先頭文字を破棄,0の場合は何もせず先頭文字を破棄,生成規則の末尾まで到達したら先頭に戻る,という操作を繰り返します.

停止条件としては記号列がある長さ以下になるときか,後述のタグシステムの模倣時は停止文字の生成規則を読まれた時に停止します*8

循環タグシステムの例は次のようになります.初期記号列10100,生成規則{001, 1010, 000}に対し,

 生成規則 | 記号列
    001   | 101
   1010   |  01001
    000   |   1001
    001   |    001001
   1010   |     01001
    000   |      1001
    001   |       001000
   1010   |        01000
    000   |         1000
    001   |          000000 (以下空文字になるまで繰り返し)

というように動作します.

循環タグシステムタグシステムを模倣することは簡単に示すことができます.

記号 \{a_1, \dots, a_n\} 生成規則\{R_1, \dots, R_n\}タグシステムに対し,各記号を長さnの{100...0, 010...0, ... ,0...001}といった記号列とみなした初期記号列と生成規則を作ります.生成規則に対してn個の空文字を追加し,元のタグシステムの停止文字を読んだ時に停止するようにすることでこの循環タグシステムは変換元のタグシステムを模倣します.

具体例を見てみましょう.記号{a, b, H}(Hは停止記号),生成規則{a: abH, b: H},初期記号列abのタグシステムを循環タグシステムに変換すると次のようになります.

記号の変換: a -> 100, b -> 010, H -> 001
生成規則: {100 010 001, 001, stop, -, -, -}
初期記号: ab -> 100 010

生成規則    | 記号列
100 010 001 | 100 010
        001 |  00 010 100 010 001
       stop |   0 010 100 010 001
         -  |     010 100 010 001
         -  |      10 100 010 001
         -  |       0 100 010 001
100 010 001 |         100 010 001
        001 |          00 010 001 100 010 001
       stop |           0 010 001 100 010 001
         -  |             010 001 100 010 001
         -  |              10 001 100 010 001
         -  |               0 001 100 010 001
100 010 001 |                 001 100 010 001
        001 |                  01 100 010 001
       stop |                   1 100 010 001 (停止)

Glider System

Rule 110がTuring完全であることを示す最後の鍵となるのはGlider Systemです.Glider Systemは一次元上で速度と方向が与えられたグライダーが時間経過とともに移動していきます.グライダー同士が衝突したとき,探索テーブルをもとに衝突したグライダーたちが変化していく計算モデル(?)です.

Glider Systemは実験的な素粒子物理や実験的なセルオートマトンと強い類似性があるそうです.

Glider Systemで循環タグシステムを模倣することを考えます.テープデータとして動かないグライダー(データグライダーと呼ぶことにします)を考え,それに対して,右側から生成規則のグライダーを流し,1のデータグライダーに衝突した時にテープデータの末尾(左端)に生成規則のかたまりを追加,0のテープデータグライダーに衝突した時にその生成規則のひとかたまりを削除することができれば循環タグシステムを模倣できそうです.

より厳密に考えてみましょう.模倣のために必要なグライダーは0と1のデータグライダー,0と1の追加グライダー,0と1の移動グライダー,先導グライダー,固定グライダー,拒否グライダー,受理クライダー*9です.

循環タグシステムを模倣するGlider Systemでは,左側から固定グライダーが十分量流れ,データグライダーが初期状態として与えられ,右側からは循環タグシステムの生成規則に従って追加グライダーと先導グライダーが十分量流れてきます.先導グライダーは生成規則のかたまりの区切りごとに挟まれ,一番初めにデータグライダーと衝突します.

先導グライダーが0のデータグライダーと衝突したとき,2つのグライダーは1つの拒否グライダーに変化します.拒否グライダーは追加グライダーと衝突すると追加グライダーを吸収します.最終的に拒否グライダーは先導グライダーと衝突し,先導グライダーに吸収されます.

先導グライダーが1のデータグライダーと衝突したとき,2つのグライダーは1つの受理グライダーに変化します.受理グライダーは追加グライダーと衝突すると,自身はそのままで,追加グライダーを移動グライダーに変化させます.最終的に受理グライダーは先導グライダーと衝突し,先導グライダーに吸収されます.

移動グライダーはデータグライダーと衝突しても何もおこさず通り過ぎ,固定グライダーと移動グライダーが衝突するとデータグライダーに変化します.

これらの衝突時の規則をもうけることによって循環タグシステムを模倣することができます.

初期記号列1,生成規則{11, 0}の循環タグシステムを模倣するGlider Systemを図にすると次のようになります.

f:id:Qoiwinski:20191211041605p:plain
循環タグシステムを模倣するGlider Systemの例(時間変化を下に連続して書いている)

青と赤の太線が0, 1のデータグライダー,青の縞々と赤の縞々が0, 1の追加グライダー,青と赤の細線が0, 1の移動グライダー,黒の点線が先導グライダー,黄土色が固定グライダー,水色が拒否グライダー,ピンク色が受理グライダーです.実際に模倣できていることが見られますね.

Rule 110のグライダー

ここでRule 110の話に戻りましょう.Rule 110をランダムな初期条件で長く見ると次図のようになります.

f:id:Qoiwinski:20191211042733p:plain
Rule 110をひたすら繰り返す様子

上図で見られるように,グライダーのようなものがいくつか散見され,その中にも固定グライダーのようなもの,交わってもお互い変わらず通り過ぎることができるもの等,特徴的なグライダーも複数種類見られます.Rule 110においてグライダーとみなせるものは30弱ほどの種類があります.これらをうまく組み合わせることによってGlider Systemを模倣できるそうです.

これらの話を厳密にしようとすると,同じグライダーでも衝突の高さの違いで生成するグライダーが大きくことなるため,どのように衝突させるべきか,そのためのグライダーの周期といった非常に複雑な話になってしまうのでこの記事では割愛させていただきます.

Rule 110は非常に小さな規則で構成されるので,Rule 110のTuring完全性は小さな計算モデルがTuring完全であることを示すのに非常に大きな貢献をします.実際に,記号数や状態数の少ないTuring機械の完全性を示す手法として,そのTuring機械がRule 110を模倣できることを示す,といったこともされています.

おわりに

Advent Calendarに登録したときは軽くPDAの話でも書くかと思っていたのにPDAが講義で扱われると知って別の話を探す事になり,大変でした….

小さな計算モデルがTuring完全なことを示せるのはとても面白いですね.Rule 110におけるグライダーの話,興味はありますが読む気にならないので誰かに教えてほしいです.

他に小話として,マリオメーカーがTuring完全であることを示す手法として循環タグシステムを用いる手法があるそうです.こういったどこかで耳にした話がつながるのも面白いですね.

明日は七果さんの記事です.楽しみだなあ〜.

*1:Coombes, Stephen. "The geometry and pigmentation of seashells." Techn. Ber. Department of Mathematical Sciences (2009).

*2:Manukyan, Liana, et al. "A living mesoscopic cellular automaton made of skin scales." Nature 544.7649 (2017): 173.

*3:ライフゲームの世界1【複雑系】 - ニコニコ動画]

*4:Four Classes of Behavior: A New Kind of Science | Online by Stephen Wolfram [Page 231]

*5:要出典

*6:Cook, Matthew. "Universality in elementary cellular automata." Complex systems 15.1 (2004): 1-40.

*7:当初の提唱モデルは空文字列になったときのみ停止し,この停止条件のみだとTuring完全にはならない.

*8:元論文に停止についての言及がなかったのでこの計算モデルで妥当そうな停止条件を追加しています.

*9:日本語の資料が無いため独自の命名になっています.