カードゲーマー向けあまり正しくない「チューリング完全」解説

まえがき

はい、noteを登録だけして全然動かしていなかったαrufαです。
初めての話題は「チューリング完全」について。いや、その、私みたいな数学力3の雑魚が話していい内容ではあまり無いのですが。
先日ハイチュウリツ氏の記事にて縁あって海外論文の翻訳のお手伝いをさせていただきました。
作業を進める中で、「マジック・ザ・ギャザリングは比較的ポピュラーなカードゲームでありながら、内容はガッチガチの数学なので、恐らく(普通に遊んでいるだけの)カードゲーマーにはあの文章の意味は届かないのでは？」という危惧が個人的に湧いてきまして。
内容的にこれがカードゲーマーに伝わって何か得あるんかと訊かれたら回答には困ってしまいますが、まぁなんとなく、自分の遊ぶゲームが「こんなことできるんだ」と思っていただければ嬉しいなという次第。
論文の翻訳や解説につきましては氏の記事にお任せするとして、こちらのページでは前段階として、ざっくりした範囲で「そもそもチューリング完全ってなんぞや」という話をさせていただければなと。また、知識がそこそこある方々に於かれましては、数学に慣れ親しんでいない人向けへの必要性とわかりやすさを優先するために数学的、歴史的に厳密な部分について、その大部分を端折ることをお許しください。

計算とは

本題の前に、前提知識として「計算」ってそもそもなんなんだろう、という話が必要です。
皆さん方は小学校で習う、「四則演算」、あるいは「加減乗除」を憶えていますでしょうか。平たく言えば足し算、引き算、掛け算、割り算のことです。
足し算で　2+3　とあれば答えは5です。
引き算で　10-4-3　とあれば答えは3です。
混ぜ合わせて　4+7-9　とあれば答えは2です。
どうして答えが出たのでしょうか、もちろん、それは「計算」したからです。
では計算とはなんでしょうか、それは、「出された情報を、ルールに合わせて操作して、答えを取り出す行為」です。
数は1，2，3，4，5，6，7…　と続いています。
2+3とあれば、これは「2から始めて3つ進める」という意味です。
10-4とあれば、これは「10から始めて4つ戻る」という意味です。
ここにある数字を100にしても1000にしても、進めるか戻るかの数が変わるだけなのはなんとなくわかると思います。
ルール部分だけ取り出す(数学ではこれを「一般化」と呼びます)と、
「1つ目の数から始めて、２つ目以降の数は『+〇』とあれば〇だけ進める、『-〇』とあれば〇だけ戻る」と書けばいいでしょう。
掛け算や割り算も同様に書けますが、ルールだけ書くと長くてややこしいのと、後で違う使い方をしたいので割愛します。
ここで重要なのは、「先に決まっているのはルールと操作手順の方で、入れる数の方は後回しでもいい」ということです。
数学の計算には、いろんな種類があります、先に書いた「四則演算」や、中学校で習い始める「関数」、高校数学の集大成と言われる「微分積分」なんてのも、全てルールがあって、ルールに合わせた操作手順があります。
そして、人類の中で賢い人たちはこう考えたわけです。「コレ手順が解れば誰でもできるし、ルールだけ先に教えたロボット作れば楽じゃね？」と。

チューリングマシン登場

そして、賢い人の一人であるアラン・チューリングという数学者が、「計算のルールと操作手順の全てを詰め込んだロボット」である「チューリングマシン」を思いつきます。実際のところこの時点で実物は存在しません。というか「それっぽいもの」は作れますが本当に完全なチューリングマシンは作れないと言うべきなのですが。
ただ、その結果として「それっぽいもの」の研究分野がものすごく進歩します。現代の電卓やパソコンは、この分野の発達で出来たものだと言っていいでしょう。
そしてさらに研究が進み、「『無限の桁数を扱う方法』と『特定の計算のルールと手順』をマスターしたら、チューリングマシンになる」ということが判明します。
なぜそうなったかはちょっと難しいですが、割と重要なので少しだけ説明します。
例えば、ここに「並んでるリンゴの数を数えるロボット」を用意します。
ロボットの前に3個リンゴを並べたら、ロボットは「3」まで数えます。
このロボットのスイッチを止めずに別のリンゴを5個並べたら、ロボットは続きから数え始めるので「8」と数えます。
つまり、このロボットは「数える」ことしかできないのに、人間がうまく操作することで3+5の足し算が出来たことになります。
次に、このロボットの前に8個リンゴを並べます。当たり前ですが「8」まで数えますが、ここで「3」を数えた瞬間に一回ロボットのスイッチを切ります。そしてもう一度スイッチを入れると、今度は続きだけを数えて「5」まで数えて止まることでしょう。
すると、このロボットは人間の操作によって8-3の引き算が出来たことになるのです。
つまり、「数えるロボット」は、工夫して使えば「足し算と引き算が出来るロボット」となるのです。
この、工夫して使えば出来る計算が増えるというのが重要で、今回の例の「数えるロボット」では無理ですが、それとは別に「めっちゃ工夫できる計算ルールと手順」が見つかったことにより、チューリングマシンは現実性を帯びていきます。何せ「あらゆる計算ルールを入れないといけない」と思われていたのに、「少ない幾らかのルール(実は1つでもいけるルールすらある)だけで作れそうだ」となったのですから。

「完全」への道

ただ完全なチューリングマシンは作れません。なぜなら「無限の桁数を扱う方法」が存在しないからです。ただ、「無限」は無理でも「めっちゃ多い桁数(現代は頑張ったら数兆桁まではいけるらしい)」ならなんとかなります(これが前段で示した「それっぽいもの」の正体です)。なので実物の計算機としてはそこそこの桁数で我慢した上で、『工夫して使ったらすべての計算ルールに化ける、幾つかの計算ルールの集まり』を以って「チューリング完全」と呼ぼうということになりました。
これにより、「チューリング完全になる計算ルールを新しく作る」という動きも出てくるようになり、今日のプログラム言語の下支えとなっています。
そして、「計算ルール」は形を変え、私たちが遊ぶ様々なゲームの中に出てきたりするようになりました。
ボードゲーム、カードゲーム、電子ゲームなどなど、ゲーマーは多くのルールに囲まれてプレイしていると言っても過言ではありません。
そしてその中の賢い人たちは、こんなことに気づくのです。「あれ？このゲームのルール『チューリング完全』じゃね？」と。

見つけ出される「完全」

チューリング完全になる計算ルールを新しく作る動きもある中で、そういうルールを意図して作っているケースも在り得なくはないですが、往々にしてそんなことを考えてゲームを作っているメーカーは少数派でしょう。
ただ面白いゲームを作ろうとしたら、チューリング完全、あるいはそれに近いルールを搭載してしまった、また、そういう場合「工夫できる計算ルール」であるためにプレイヤーに工夫されて想像を絶するプレイ画面が飛び出してきた、なんて事態が起こります。挙句さらなるルールの駆使によってゲームそのものを計算ツールとして使ってしまう、なんて芸当をするプレイヤーもいます。
先に示した解説記事も、元はと言えばそんな工夫の産物です。「いろんなことが出来るゲーム」とは、「何が起こってもおかしくないゲーム」でもあるのです。もしかしたら、記事を今読んでいらっしゃる貴方が、次の工夫の発見者になるかもしれませんね。

おわりに

如何だったでしょうか。気が付いたら3000文字を超えていました。それなりに厳密な話をザクザクと切り捨てながらですが、それでも結構難しい内容を長々と書いてしまいました。
ただ今回のコンセプトとして、ハイチュウリツ氏の記事の事前知識として、また、私たちが遊ぶゲーム、そしてそのゲームのルールには、メーカーのたゆまぬ努力と、プレイヤーの工夫と、そして思わぬ副産物が眠っているんだ、ということを知ってくれたら幸いです。
またこの記事を書くきっかけであり、海外論文の翻訳協力という得難い経験をさせていただいたハイチュウリツ氏に、改めて謝辞を述べさせていただき、今回の記事の〆とさせていただきます。