2020-12-03

理情3Sの所感

もう8月も終わりですが、いくつか成績が出てようやく3Sが終わった気持ちになってきたので備忘録として3Sをまとめておきます。理情ってどんなことをやってるのかなと参考になれば幸いです。

全体を通して

新型コロナウィルスの影響ですべての講義がオンラインとなりましたが、情報科学科は学科として先陣を切る思いで（？）4月の初週からオンライン講義を行いました。教員の方々もパソコンに弱いということはなく、滞りなくオンライン授業が行われました。

ほとんどの授業がスライドの画面を配信してそれの説明を行う形で、適宜別資料を写したり、画面に書き込んだりして説明をされていました。スライドは講義資料として配布されており、学生の要望もあってか、セメスターの後半には全ての座学の講義録画がITC-LMSから視聴可能になりました。講義の復習がしやすくとても快適でした。

3Sの時間割は2限に座学、（水曜を除いて）3, 4限に実験・演習という形でした。先輩方から3Sはキツイと聞かされていた通り、課題の量が多く、セメスター始めはその日のうちに課題を終わらせて「意外とホワイト」とか言っていたものの5月末から破滅が始まりました。

破滅が始まってからの生活は週末になるべく多くの課題を終わらせて、平日は翌日提出の課題の発展を眺めたり、週末に終わらせられなかった必須課題を終わらせたりで課題の自転車操業になっていました。翌日提出分の課題を終わらせると達成感から脱力してYouTubeを見ていました。今思うと、これのせいで座学の復習が疎かになっていたのでスケジューリングが下手としか言いようがないですね…。

例年は地下（学生控室）があって、実験や演習を詰まらせたりバグらせたりしたときにそこで学生同士で助け合える（らしい）のですが、今年はそれがなく厳しい戦いとなっていました。しかし、オンライン化への対応とのことで座学の課題が減らされていたようなので、環境が悪かったのか自分が課題をこなすのが下手だったのか不明なままです。

3Sの講義

前提として、理情3Sは必修のみを取る人がほとんどで、自分もそうでした。以下紹介する講義は全て必修の講義です。

月2 オペレーティングシステム

講義名の通りOSにまつわる話を扱いました。具体的には、プロセス管理、スケジューリング、メモリ管理、ファイルシステムやその他OSの提供する機能等の話を扱いました。

講義を聞くのみだと、ぼんやりとした理解しか得られませんでしたが、月3, 4限に行われるシステムプログラミング実験によりよりはっきりとした理解を得ることができました。

月3, 4 システムプログラミング実験

オペレーティングシステムで扱った話を実際の計算機上で扱って理解していこうというコンセプト（のはず）の実験でした。前半と後半で内容が分かれていて、前半は既存のOSのサービスを利用する内容で、後半はベアメタルプログラミングといってOSが乗っていない計算機をちょっと動かす内容でした。

前半のOSのサービスを利用する話では、マルチスレッド、ソケット、自作シェル（プロセスの実行、パイプ処理、ジョブ管理）といった話を扱いました。マルチスレッド回にpthreadを使わないマルチスレッドの実装が発展課題としてありましたが、結局諦めてしまったのでいつかやらないとなあと思っています。

後半のベアメタルプログラミングは、今年内容が刷新され、TAさんが新しく環境を構築してくださり、その上で色々（時間ごとのプロセス切り替え、仮想メモリの実装）やりました。

どの回も、スライドに初めて目を通したときには「何が書いてあるかよくわからない」という状態になるものの、丁寧に読んで自分で適宜調べて実装していき、最終的に課題が提出できる形になると、スライドの内容が「なぜわからなかったのかがわからない」状態になったので、とても良く出来てるカリキュラムだなと感じました。

火2 離散数学

グラフ理論はほどほどに、線形計画法がメインの講義でした。自分は講義だけではあまり理解できず、金3, 4の離散数学演習のおかげでなんとかなっていました。なんとかなってないかも。例年は試験ですが、今年はレポートで評価となりました。

火3, 4 関数・論理型プログラミング実験

7割OCaml（関数型言語）で3割Prolog（論理型言語）でした。

2AでSchemeを扱ったおかげか、関数型言語を新しく扱うことに抵抗はありませんでした。最初の数回でOCamlの言語仕様に慣れると（ここにしれっと存在したモナド回がキツかった）、OCamlパートのメイン内容であるOCamlのインタプリタ作成回に入っていきました。

2AでもSchemeのインタプリタを作ることがありましたが、それよりずっと本格的で型推論を書いたりしました。これらの内容は木2の言語処理系論に対応していました（字句解析と構文解析はocamllexとocamlyaccに丸投げですが）。

Prologパートは初めて扱う論理型言語の特徴や処理系がどういった実装なのかを知っていくことがメインの内容になっていたと思います。発展課題のチューリングマシン作成やProlog処理系作成が楽しかったです。特に後者はOCaml インタプリタ作成の知識が大いに役に立ったのでかなり楽しめました。

最終回（最終課題）は内容が大きく変わってリバーシAIを実装せよというものでした。OCamlやHaskellが使用言語として許可されていて、なぜかRustも使用言語として許可されていました。提出された各自のAIで総当たり戦が行われ、学科内での順位がフィードバックコメントで伝えられました。

探索の深さが大事そうだったので、OCamlより高速なRustを使いました。1からRustを学習する羽目になりましたが、そのおかげかそこそこ良い順位を取れました。

水2 情報論理

計数4年の「プログラムの数理」と同一の授業です。

論理と計算可能性の話を扱いました。論理パートは完全性や健全性の話を扱い、計算可能性パートは帰納関数や帰納的可算集合、ゲーデルの不完全性定理のほんの一部を扱いました。座学の講義の中で一番好きな講義でした。

講義資料として提供されている教科書（蓮尾先生著）が非常にわかりやすく丁寧でした。英語ですが。

木2 言語処理系論

字句解析、構文解析、意味解析、中間コード生成といった話を扱いました。2Aの形式言語理論を丁寧にやっていると理解が進みやすいと思います。各解析で用いられるクラスと形式言語理論で扱ったクラスがいい感じに対応していて気持ち良くなれます。

木3, 4 ハードウェア実験

数回ブレッドボードとICを用いたちょっとした論理回路の作成を行い、それ以降はVerilogを用いた回路設計（除算回路や通信回路）を行い、それをFPGA上で動作させました。2Aのハードウェア構成法をぼんやり思い出しながらやりました。

セメスター中盤に学科PCや実験のために必要な物資が大学から各家庭に郵送され、それから開始しました。物資箱を開けたらロジックアナライザやFPGAが出てきてワクワクしました。一家に一台FPGA。

金2 計算機構成論

コンピュータアーキテクチャについて扱いました。CPUは命令ごとにどう処理する回路を持っているのか、パイプライン処理はどうなっているか、投機実行とはなにか、OoO実行とはなにか、といったCPUの仕組みから高速化の工夫まで、機能の説明だけでなく、どういった実装で実現されているのかまで踏み込んだ説明がされました。

この講義を通じてようやくCPUが魔法の箱ではなく回路の詰まった箱だと感じられるようになった気がします。

最終課題としてSpectre、Meltdownについてのレポートが課されました。数年前に話題になっていた「ハードウェアレベルの脆弱性」がどういったものなのか理解でき、同時にアーキテクチャへの理解も深められる良い題材の最終課題でした。

金3, 4 情報科学演習1

情報論理演習と離散数学演習が交互に行われていました。両方とも事前に問題が公開され、講義時間までに各自で問題を解いて発表者を決め、講義時間に問題を発表するという形式でした。

セメスター初めの余裕があった頃は空いた時間に情報論理演習をできるだけ解いていましたが、破滅と同時にほとんど解かなくなりました。離散数学演習は解けばとくほど評価に加味されるというモチベーションもあり、可能な限り解いていました。

最後に

各座学の理解が深まるような実験・演習が設けられており、とても良いカリキュラムでした。座学だけを取っている他学部他学科の人がどうやって講義内容を理解していくのかを知りたいくらいです。

実験・演習は自分で調べつつ頭を捻ることでなんとか自力で解決できるような内容がほとんどで、難易度の調整が適切でした。おかげで（？）やればなんとかなるだろうという謎の自信はつきました。

3Sが終わった今、まだCPUを作れる気はしていませんが、3Sを通じて得た謎の自信で3Aも苦しみながら生き抜いて行こうと思います。

最後に、新型コロナウィルスというこれまでに対応したことのない状況の中、我々学生たちが学びの機会を損なわないよう可能な限り対処してくださった事務員の方々や教員の方々に感謝申し上げます。ありがとうございました。

早く地下で学科民と交流できる日々を手に入れたいです。

2019-12-12

セルオートマトンと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 SystemがTag 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:ライフゲームの世界１【複雑系】 - ニコニコ動画]

*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:日本語の資料が無いため独自の命名になっています．

オンライン対戦系

Apex Legends

Counter-Strike: Global Offensive

Dead by Daylight

オンライン協力系

Deep Rock Galactic

Left 4 Dead 2

Overcooked! 2

自動化系

Satisfactory

shapez.io

サバイバル系

Raft

7 Days to Die

街作り系

Cities: Skylines

Banished

その他

Five Nights at Freddy's

Hexcells シリーズ

Baba Is You

Getting Over It with Bennett Foddy

Katamari Damacy REROLL

Risk of Rain 2

Rogue Lagacy