概説 (マジックチューリングマシン v5: 腐れ肺の再生術師 / 尖塔の大長)

(この記事は以下のページの翻訳です: http://www.toothycat.net/~hologram/Turing/)

マジック・ザ・ギャザリングはチューリング完全である

マジック・ザ・ギャザリングが複雑なゲームであることは知られている。しかし今や証明されたのである: マジックのカードを使ってコンピューターをも組み立てられる事が。

「チューリング完全」とは何を意味するか?

「チューリング完全性」という概念がある。それは、あるシステムがある特定の複雑性を備えていることを示すのに用いられる。あらゆるチューリング完全なシステムは、理論上その他のあらゆるチューリング完全なシステムをエミュレートする事が出来る。あるシステムのチューリング完全性を示す一つの方法は、そのシステム内で「チューリング機械」を作ることである。これはチューリング完全性を示す唯一の方法ではないが、理解しやすい方法の一つではある。このサイトではマジック・ザ・ギャザリングのカードを用いて万能チューリング機械を組み立てる方法を解説する。

しかし、マジックはプレイヤーによる多くの選択を伴うのでは？

その通り、本来は。しかし通常のゲームプレーにおいても時たま、カードやゲームのルールに基いて、3、4つの一連のイベントが選択肢なしに立て続けに起こる事がある。これから説明する機械では、それを無数に続く強制的な選択へと拡張する。

私の考えるマジックチューリングマシンでは、ゲームが選択肢を提示する場合を除いて、プレイヤーは全く何もしない。

ひとたびゲーム内で「機械」が動き始めると、以下で説明するある種の例外を除いて、プレイヤーの選択を全く必要とせずに処理は継続する。例外: 機械が用いるカードのうちいくつかは「あなたは[Xを行う]を選んでもよい。そうしたなら、[Yが行われる]」と書かれている。そのような場合、機械はそのプレイヤーが必ず、また唯一の方法で、Xを行えるよう準備する。そしてプレイヤーは常に提示された選択肢を選ぶ。

(「してもよい」カードを取り除く可能性に関する議論については、「今後の方向性」を見ること。)

どういう仕組？

いいことを聞いてくれた！このサイトでは機械が必要とするカードの完全なリストと仕組みについての詳しい説明を読む事ができる。この奇怪なものを作り出した人物についてもっと知ることもできる。楽しんで！