Magic: The Gatheringはチューリング完全？典拠はどこですか？

この記事について

Magic: the gathering(以下、Magic)というカードゲームはチューリング完全と言われているので、その根拠となる論文と軽い説明を書きます。

日本語の情報がとても少ないので...

(チューリングマシンを実際にどうシミュレーションすろのか、という点は論文をまだ読み終えていないので記述できません。)

関係図と解説

下の図は、Magicのゲームがどのようにチューリングマシンをシミュレートできるかを示した関係図です。

ここで、

• 「A ← B」は、「任意のAがシミュレーションできるBを構築することができる」
• 「A <...B」は、「あるAと等価なBを構築することができる」

を意味します。ただし、この2つにチューリング完全性に関する特別な違いは無いと思われます。

• Shannonさんは、あるチューリングマシンと全く等価な2記号のチューリングマシンを作れることを示しました。¹
• Cockeさんらは、2記号のチューリングマシンを上手く変化させることで、それと等価な2-タグシステムが作れることを示しました。²
• Rogozhinさんは、任意の2-タグシステムをシミュレートする、プログラムがどのタグシステムでも同じなチューリングマシンの作成法を示しました。³
• Churchillさんらは、そのチューリングマシンのプログラムを、他のクリーチャーが死亡した際に誘発する能力を持ったクリーチャーで表現し、そのマシンをシミュレートするMagicのゲームが存在することを示しました。⁴

したがって、あるチューリングマシンと等価な2-タグシステムをシミュレートできる Magic のゲームはチューリング完全です。という論法でした。

---

最後に、Magic 上でチューリングマシン(2状態18記号の)を動かしている動画を紹介します。

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

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

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

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