老害な守護者「M:tGはチューリング完全だと言っているそうだな。それをどう示してくれるのかね？」【未完成、順次更新】【1/6】

前置き

頑固じいさん「ゆっくり頑固じいさんだ」

老害な守護者 「ゆっくり老害な守護者です」

じ「守護者ぁ、我らがカードゲームの、マジック：ザ・ギャザリングがチューリング完全だって噂を聞いたんだけど、いまいち良く分からないのだが...」

守「マジック：ザ・ギャザリングはチューリング完全だと言っているそうだな。それをどう示してくれるのかね？」

じ「えっ」

守「...コホン。では、今日はチューリングマシンをマジック：ザ・ギャザリング上で動かす方法を説明していきます」

じ&守 「ゆっくりしていってね！」

この記事は？

以前、私はこんな記事を書きました：

これはマジック：ザ・ギャザリングというカードゲームがチューリング完全であることについて、その根拠となる論文をたどっていった記事です。

が、
正直そこからは全く何も感じられません...。

という事で、実際のチューリングマシンをマジック：ザ・ギャザリングの中で動かしてみる¹という記事になります。

早速、彼らが説明してくれるようですよ。²

以降では、 以下のように短縮表記をする場合があります。

「マジック：ザ・ギャザリング」 → 「マジック」
「チューリングマシン」 → 「TM」

で、そもそもチューリング完全って？

頑固じいさん「というか、わしはそもそも、チューリング完全とかいうのをふんわりとしか理解していないのだが」

老害な守護者「チューリング完全っていうのは、大雑把に言うと、チューリングマシンをシミュレートできる環境のことです」

守「具体的に言うと、マジックが以下の3つを満たせば、マジックはチューリング完全といえるわけですね」

1. あるチューリングマシンが与えられたときに、それに対応したゲームの状態を上手く作ることが出来ること
2. そのゲームで、プレイヤーが行動を決定するためのルールがあること
3. ゲームが終わった時、その状態を上手く解釈すれば、元のチューリングマシンの状態を読み取ることが出来ること

じ「えーと、チューリングマシンってなんだ？」

チューリングマシンとは？ (大雑把な解説)

折り畳み

守「チューリングマシンとは、昔の偉い人が考えた入力を計算する仮想的な機械です」

守「この機械は、テープと制御装置の二つから構成され、ルールによって計算を進めていきます」

じ「？？？」

守「例を出しましょうか。下の図を見てください。」

守「まず最初に左右に無限に続いていくテープ を用意します。」

守「あ、テープって言ってもカセットテープのような細長い紙ですよ。」

じ「最初からすごいことを言っているな」

守「仮想的な機械ですから。そのテープは、一定の長さごとにマス目で分けられています。このマス目一つごとに一つ、好きな記号 を書くことが出来ます。記号にはアルファベットを使うことが多いです。」

守「テープには、まず最初に、入力とする記号の列を書いておきます。そして、余った左右の空白に何も書いていないことを表す、特別な記号を、無限に書いておきます。」

じ「上の図だと、入力が、 $ABAB$ で空白記号が $S$ であるという事か。なるほどテープは無限の長さだから、左右を空白記号が無限につながっていることにしないといけないんだな。しかし、ただの紙切れが出来ただけで何が嬉しいんだ？」

守「ここから面白くなります。チューリングマシンは、あと制御装置を持っている、と言いましたね。制御装置は、以下の行為を可能な限り繰り返すだけの装置です。」

1. 今指している場所を読む。
2. 読んだ記号と現在の内部状態によって、①内部状態を変化させ、②記号を今指している場所に書き、③読んでいる場所を左と右に動かす。

守「 内部状態(Internal state) とは、ある特定の値です。この値ごとに動き方を変えます。」

じ「内部状態ってのは上の図だと q1 だか q2 だかってやつのことか？」

守「そうです。内部状態の表現には、基本的に$q$ を使うことが多いですからね。では、制御装置の動きを見守ってみましょうか。最初の内部状態を q1 としておきます」

①：動作開始。今指している場所を読む。読んだ記号がAで、内部状態がq1のルールを探す。ルールは、「内部状態をq2に 変えて、指している場所にBを書き、右のマスに指している場所を動かす」ようにしろと書いてあるので、その動作をする。

②：今指している場所を読む。読んだ記号がBで、内部状態がq2のルールを探す。ルールは、「内部状態はq2 のままで、指している場所にAを書き、右のマスに指している場所を動かす」ようにしろと書いてあるので、その動作をする。

②：今指している場所を読む。読んだ記号がAで、内部状態がq2のルールを探す。ルールは、「内部状態をqfに 変えて、指している場所にBを書き、右のマスに指している場所を動かす」ようにしろと書いてあるので、その動作をする。

④：受理状態。qf はあらかじめ決めた特別なルールで、この内部状態になるとチューリングマシンは停止する。

じ「んーなるほど、なんとなくわかった気がする。。。受理状態って？」

守「チューリングマシンが停止していることを表す状態...と理解しておくといいと思います」

じ「「...SABABS...」 という入力を与えて、「...SBBBBS...」とい状態になって停止した、というわけか」

守「そのとおりです」

守「...あと、TMが現在持っている情報(テープ、ヘッドの位置、内部状態)をまとめて 様相(Configuration) というので覚えておいてください。」

内部状態は特定のただ１つの値です。テープや内部状態とかの、TMの全部の情報をまとめたものではありません。様相との混同に注意してください。

チューリング完全であると何がうれしいのか

じ「...で、チューリングマシンってやつはなかなか面白そうな機械だったが、結局何の役に立つんだ？」

守「もう一度、図を見ながらチューリング完全というのが何かを思い出しましょう」

じ「次の3つが成り立てばチューリング完全ってことだったな」

1. あるチューリングマシンが与えられたときに、それに対応したゲームの状態を上手く作ることが出来ること
2. そのゲームで、プレイヤーが行動を決定するためのルールがあること
3. ゲームが終わった時、その状態を上手く解釈すれば、元のチューリングマシンの状態を読み取ることが出来ること

守「そうですね。上の図では、これらの条件を矢印に対応させました。これらが成り立つと、チューリングマシンをマジックの上で動かしていると言えませんか？」

じ「確かに、そんな感じがするな...。それで、チューリング完全だと何が嬉しいんだ？」

守「昔の偉い人は、チューリングマシン完全なものの上で計算できるかどうか を、計算可能かどうかの基準にしよう、と言いました。」

守「マジックがチューリング完全であるという事は、一般的に計算できるとされているあらゆる計算が、マジックの上でできるという事になるのです。」

じ「えーとつまり、マジック上で、パソコンと同じ計算ができる という事になるのか」

守「...そうなんですけど、呑み込みが早すぎないですか...？」

実際の変換

老害な守護者「さて、上の章では簡単に説明しましたが、実際に行われる変換や解釈は下の図のようになります。」

頑固じいさん「うわ、思ったより長いじゃないか...」

守「ええ、すごく長くて、これの１つ１つの矢印について説明していく必要があるんです。ほぼ形式的な変換なのでこの説明の仕方だと逆に疲れるので...」

地の文で、各矢印について説明をしていきます。
(途中で解説が必要になった時、また彼らを呼びます)

本当に任意のTMが変換できるかどうかの証明は各論文に任せればいいので、ここでは実際の、特定のチューリングマシンを変換することで動かせることを示します。

今回変換の対象にするのは、以下のチューリングマシンです。

• ルール

現在の内部状態	読んだ記号	変化先の内部状態	書く記号	動く方向
$q_1$	A	$q_1$	B	右
$q_1$	B	$q_1$	B	左
$q_1$	C	$q_f$	A	左

• 初期状態: $q_1$
• 受理状態: $q_f$
• 空白記号: $C$
• 最初のテープ: $…CCC\underline{A}CCC…$
• 最初のヘッド位置: ↑の下線の位置

このTMの様相は、以下のように変化していくはずです。
$(…CCC\underline{A}CCC…, q_1) \rightarrow (…CCCB\underline{C}CC…, q_1) \rightarrow (…CCC\underline{B}ACC…, q_f)$

以降

以降では、各記事につき一つずつシステムの構成法を示していきます。

（下に示す記事の１つを読むとき、その１つ前の記事を同時に開いて構成や様相を確認しながら読むと良いです。）

1. 全体的な解説（この記事）
2. 任意のTM ⇔ 2記号TM ³
3. 2記号TM ⇔ 先書きTM ⁴
4. 先書きTM ⇔ タグシステム（まだ）⁴
5. タグシステム ⇔ 2状態18記号のTM（まだ）⁵
6. 2状態18記号のTM ⇔ マジック（まだ）⁶

ライセンス

この記事で使われている一部の画像は、Magic:the Gathring のカードイラストから切り抜いたものです。Wizards of the Coast社の認可/許諾は得ていません。

1. ただし、愚直にやると入力がとてつもなく長くなるので、必要に応じて変換を分離します。 ↩

2. 真面目に解説をしようとすると、長すぎてだんだん説明が上滑りしていきそうなので、対話形式でやります。 ↩

3. SHANNON, Claude E. A universal Turing machine with two internal states. Automata studies, 1956, 34: 157-165. ↩

4. COCKE, John; MINSKY, Marvin. Universality of tag systems with P= 2. Journal of the ACM (JACM), 1964, 11.1: 15-20. ↩ ↩²

5. ROGOZHIN, Yurii. Small universal Turing machines. Theoretical Computer Science, 1996, 168.2: 215-240. ↩

6. CHURCHILL, Alex; BIDERMAN, Stella; HERRICK, Austin. Magic: The gathering is Turing complete. arXiv preprint arXiv:1904.09828, 2019. ↩