はじめに

Minecraftがチューリング完全だと風の便りで聞き、本当かな？と思って色々調べてみました。

この記事にはMinecraftのコマンドブロックとか、レッドストーン回路の話とか、ほとんど出てきません。へんてこな記事になっていると思いますが、あしからず。

最初に「チューリング完全」の説明をしてから、本題に入ります。チューリング完全が何なのか既に知っている人は、この項目は飛ばしてください。

「チューリング完全」って？(やわらかめ)

「計算機」には色々なものを考えることができます。足し算しかできない計算機とか、"0"と出力することしかできない計算機とか。そんな計算機たちの中でも、めちゃくちゃすごくて、他の計算機が計算できることは何でも計算できる「スーパー計算機」を考えましょう。

ある計算機がこの「スーパー計算機」と同じ能力を持つとき、その計算機は「チューリング完全である」といいます。つまり、「チューリング完全」である計算機は、他の計算機ができる計算なら何でも模倣(再現)できるのです。すごい！

「チューリング完全」って？(かため)

概要

1936年にイギリスの数学者であり計算機科学者でもあるアラン・チューリングが、チューリングマシン(以下、TM)という仮想機械を発表しました。この機械は、「計算」とは何なのか、「計算機」とは何なのかを科学的に議論するための、理想化された機械であり、

読み書き可能な無限に長い1本のテープ

テープの中に格納された情報を読み書きするヘッド

機械の内部状態を記憶/制御する制御部(有限オートマトン)

で構成されています。テープは同じ大きさの区画(セル)に区切られており、それぞれの区画には、ヘッドを使用してテープ記号を読み書きすることができます。テープ記号については後述します。

また、TMは内部状態とヘッドから読み出した情報の組み合わせに応じて、次の動作を実行します。

ヘッド位置のテープに情報を書き込む

機械の内部状態を変える

ヘッドを右か左に一つ移動する

形式的な定義

TMについて形式な定義を行うと、次の7項組となります。

M = <Q,Σ,Γ,δ,b,q_0,q_f>
$Q$：状態の有限集合

$Σ$：入力アルファベット

$Γ$：テープ記号 $(Σ \subset Γ)$

$δ$：遷移関数

$b$：空白記号 $(b \in (Γ-Σ))$

$q_0$：初期状態 $(q_0 \in Q)$

$q_f$：受理状態 $(q_f \in Q)$

遷移関数$δ$は、$(Q \times Γ) → (Q \times Γ \times d)$への写像です(ただし、$d \in $ { $L,R$ })。

例えば

δ(q,a) = (r,b,R)

は、「現在の状態が$q$であり、ヘッドの先の記号が$a$であれば、状態を$r$に移し、ヘッドの先に記号$b$を書き込んでから、ヘッドを$R$方向(右方向)に1つずらす」ことを意味しています。

また、後の記述のために、$Σ$のスター閉包$Σ^\star$を定義します。スター閉包とは、長さが0である空記号列$ε$を含めて、$Σ$上で作り得るあらゆる記号列の全体からなる無限集合を表します。

例えば、$Σ=${ $0,1$ }であるとき、$Σ^\star = ${ $ε,0,1,00,01,10,11,000,001,010,…$ }です。

動作

入力文字列$w( \in Σ^\star )$に対するTMの動作は以下の通りです。

まず最初に、テープ上の連続した区画に入力記号列$w$が書き込まれたものが用意され、ヘッドは$w$の左端に置かれます。なお、そのほかの部分には空白記号$b$が書き込まれています。さらに、機械の内部状態が初期状態$q_0$に設定され、TMの動作が開始されます。その後は遷移関数$δ$に記載された動作に従って逐次動作が続けられます。

TMの現在の状態が$q$であり、ヘッド先の記号が$a$であって、$δ(q,a)$が定義されていない場合、TMはそこで動作を停止します。TMが停止したとき、その状態が受理状態$q_f$であれば、$w$はTMにより受理されるといいます。また、$w$がTMにより受理されない場合とは、

受理状態へ至らずに最終的な計算状況へ到達したとき

最終的な計算状況へ到達せずに、永遠に計算を続ける状況であるとき

であり、かつこのときに限られます。

万能チューリングマシン

遷移関数には様々なものを考えることができます。

例えば、$q \in Q ,\forall x \in Σ$に対して、次の遷移関数

δ(q,x) = (q,`0',R)

は、内部状態やヘッドの先の記号が何であろうとも、ヘッドの先に記号$`0'$を書き込んでから、ヘッドを$R$の方向に1つずらす関数を示しています。このような遷移関数を持つものもTMの一つですが、これでは計算能力が低いといえます。

ここで、遷移関数をうまく構成すると、「いかなるTMであろうとも、それを模倣することが可能な、あるTM」が作成可能になります。つまり、他のTMが計算可能であるどのような計算でも、計算可能なTMが作成可能ということです。このようなTMを万能チューリングマシンといいます。

そして、ある計算のメカニズムが万能TMと同じ計算能力を持つとき、その計算モデルはチューリング完全であるといいます。

チューリング完全の説明は以上です。お疲れさまでした。

「チューリング完全」であることを示すには？

Minecraftがチューリング完全であることを示すには、Minecraft上で「既にチューリング完全であると分かっている"何か"」を模倣できれば良いことになります。なぜなら、その"何か"を模倣すれば、間接的にあらゆるTMの計算を模倣できるためです。

例えば、チューリング完全であるものとして、以下のようなものがあります。

一般的なプログラミング言語全て

純LISP

SQL

HTML5 + CSS

ウルフラムの2状態3記号チューリングマシン
(イギリスの学生さんがチューリング完全性を証明しました。なんと証明当時は20歳！)

ポケモン黄色
(バグを利用することによって、ゲーム操作によりアセンブリを書き換え、チューリング完全性を満たすゲームに書き換えることができるそうです。)

マジック・ザ・ギャザリング

We always knew Magic: the Gathering was a complex game. But now it's proven: you could assemble a computer out of Magic cards.
マジック・ザ・ギャザリングが複雑なゲームであることは知られている。しかし今や証明されたのである: マジックのカードを使ってコンピューターをも組み立てられる事が。
(リンク先より)

いろいろありますね。中には、「え？」と思うものもありますが…。

しかし、これらをMinecraft上で実装するのは厳しそうです。そこで、何か他にチューリング完全であるものを実装している人はいないかと調べてみると、いくつか見つかりました。その概要とともに紹介したいと思います。

実装例

Brainf*ck

概要

Brainf*ckは、コンパイラがなるべく小さくなる言語として考案されたプログラミング言語で、可読性が非常に低いですが、チューリング完全です。俗語が含まれるためよく伏字にされます。

Brainf*ckプログラムは、以下の8個の命令から成り、それ以外の文字は無視され、読み飛ばされます。

> ポインタをインクリメント
< ポインタをデクリメント
+ ポインタが指す値をインクリメント
- ポインタが指す値をデクリメント
. ポインタが指す値を出力
, 入力から1バイト読み込み、ポインタが差す先に入力
[ ポインタが指す値が0なら、対応する]の直後にジャンプ
] ポインタが指す値が0でないなら、対応する[の直後にジャンプ

プログラム例

Brainf*ckによる"Hello, world!"プログラムです。

+++++++++[>++++++++>+++++++++++>+++++<<<-]>.>++.+++++++..+++.>-.
------------.<++++++++.--------.+++.------.--------.>+.

わかりませんね。

紹介

Brainf*ckを実行できるコンピュータ、あるいはインタープリタを実装されています。

ライフゲーム

概要

ライフゲームは、1970年にイギリスの数学者ジョン・ホートン・コンウェイが考案した、生命の誕生、進化、淘汰などのプロセスを簡易的なモデルで再現したシミュレーションゲームであり、セル・オートマトンのもっともよく知られた例でもあります。

セル・オートマトン

セル・オートマトンとは、格子状のセルと単純な規則による、離散的な計算モデルです。有限種類の状態を持つセル(Cell、細胞のような単位)によってセル・オートマトンは構成され、次々に個々のセルの状態が変化します。その変化は、ある時刻$t$においてのセルの状態、および近傍のセルの状態によって、次の時刻$t+1$、すなわち新たな世代での各セルの状態が決定されます。

ルール

ライフゲームでは初期状態のみでその後の状態が決定されます。各セルには「生」と「死」(あるいは「1」と「0」)の2つの状態があり、あるセルの次のステップ(世代)の状態は周囲の8つのセルの今の世代における状態により決定されます。セルの生死は次のルールに従います。

誕生：死んでいるセルに隣接する生きたセルがちょうど3つあれば、次の世代が誕生する。
生存：生きているセルに隣接する生きたセルが2つか3つならば、次の世代でも生存する。
過疎：生きているセルに隣接する生きたセルが1つ以下ならば、過疎により死滅する。
過密：生きているセルに隣接する生きたセルが4つ以上ならば、過密により死滅する。

紹介

ライフゲームをシミュレーションできる環境を実装されています。

1次元セル・オートマトン

概要

上記のセル・オートマトンの1次元版です(基本セル・オートマトンともいいます)。

基本的な動作は同じで、1次元で各セルは2つの状態(生 or 死、1 or 0)をとることができます。あるセルとその両側の3つのセルで近傍を構成するので、1つの近傍がとりうるパターンは $2^3=8$ 種類となり、規則はそれらのパターンについて、そのセルが次世代に1と0のどちら状態となるかを決定します。従って、規則群の組合せは $2^{2^3}=2^8=256$通りとなります。

それら256種類のセル・オートマトンは、一般にイギリスの理論物理学者であるスティーブン・ウルフラムが考案した0から255までのルール番号で参照され、これをウルフラム・コードと呼びます。Rule 110セル・オートマトンは、以下の規則により世代が更新していくオートマトンです。

現在の状態	中央のセルの次の状態
0 0 0	0
0 0 1	1
0 1 0	1
0 1 1	1
1 0 0	0
1 0 1	1
1 1 0	1
1 1 1	0

「Rule 110」と呼ばれているのは、中央のセルの次の状態を並べると01101110となり、この2進数を10進数に直すと110となるからです。

例えば、以下のようなビット列があったとします。

…100111011001…

このビット列に上に記載した規則に従って操作を行うと、以下のようになります。

…101101111011…

両端は無限に0が並んでいるとします。分かりやすいように一部を強調して表示してみます。

…1001 110 11001…
　　　　↓
…10110 1 111011…

こんな感じで、際限なく計算を繰り返します。

これらのセル・オートマトンの挙動を見るために、三角形のような図形を描画することがあります。描画される図形は、1ヶ所だけ1にした初期状態からの、セル・オートマトンの変化の様子を示しており、図の各行がセル・オートマトンの1世代の履歴です。また、一番上の行が$t=0$であり、各ピクセルは、0を白、1を黒で描画しています。

Rule 90の1次元セル・オートマトンは、この図形が典型的なフラクタル図形であるシェルピンスキーのギャスケットとなります。

現在の状態	中央のセルの次の状態
0 0 0	0
0 0 1	1
0 1 0	0
0 1 1	1
1 0 0	1
1 0 1	0
1 1 0	1
1 1 1	0

紹介

実はRule 110のセル・オートマトンは、チューリング完全であることが知られています。以下の動画では

Rule 126

Rule 30

Rule 110

Rule 150

のセル・オートマトンが紹介されます。

YouTube - Elementary Cellular Automaton In Minecraft

その他

そもそもCPUやワードプロセッサをMinecraftで作ってしまったという人が結構多いです。すごい…

さいごに

というわけで、Minecraftは~~余裕で~~チューリング完全のようです。コマンドブロックやレッドストーン回路を駆使すれば何でもできそうですね。(調べている途中で、Minecraftでパックマンを実装したとか、ポケモン赤を実装したとかも出てきました。もはや訳が分かりません。)

気が向いたら自分でもMinecraft上でセル・オートマトンとか実装してみたいなと思います。

参考文献

オートマトン言語理論計算論〈1〉 (Information & Computing) J．E．ホップクロフト,R．モトワニ,J．D．ウルマン著野崎昭弘,高橋正子,町田　元,山崎秀記訳サイエンス社
Wikipedia - チューリングマシン
Wikipedia - チューリング完全
ニコニコ動画 - マリオメーカーはチューリング完全だった【万能計算機】
「文献」といっていいのかわかりませんが、参考にさせていただきました。

Minecraftってチューリング完全らしいよ