Duel "Math"ters特別編 ～絶望神サガでわかるwhile文～

ごあいさつ

　どうも、大きな数の勉強してたら「再帰」について死ぬほど勉強する羽目になったαrufαです。
　今回は特別編。数学っちゃ数学なんですが、計算とか数式とかとはちょっと違うプログラムのお話。特に「再帰関数」と呼ばれる物についてのお話。タイトルの通り絶望神サガがどんだけヤバいことしたかを数学目線で、その上でわかりやすく(数学上の厳密性は案の定犠牲になりますが)お話できればなと思います。

再帰って？

　簡単に言えば「特定の決まり事の中で同じことを繰り返す」行為のことです。現実に存在してイメージしやすい物としては「椅子取りゲーム」や「テニス」とかが該当するでしょうか。ちょっとだけ数学目線で話すなら中学校で習う「数列」は再帰のお話だったりします。忘れている人もいると思うのでちょっとだけご紹介。
a_1=1
a_(n+1)= a_n + 2　(nは自然数。1,2,3,4,5,6,7,8…. って続くやつ。)
といった数式があるときに、a_1,a_2,a_3,a_4…と並べると
1,3,5,7,9,11…
と続いていきます。これはa_1で「初項(並びの最初)」と「次項(次の数はどう計算するか)」を決めることで、次項の計算式を『何回も繰り返せる』、というものです。試しに次項の式を3回繰り返すと
a_(n+1) = a_n + 2　・・・①
a_(n+2) = a_(n+1) + 2　・・・②
a_(n+3) = a_(n+2) + 2　・・・③
②に①を入れる　a_(n+2) = a_n + 2 + 2　・・・④
③に④を入れる　a_(n+3) = a_n + 2 + 2 + 2 = a_n + 6
と、まぁこんな感じですね。3回分の増加量が1つにまとまったのがわかってくれればOKです。
　似たようなことは数列に限らず、いろんな関数でもできます。これは少し前にデュエル・マスターズの最大パワーを求めた時にも使った「ネスト」という考え方で、これも繰り返しを行うものなので、再帰の仲間です。
f(x)を f(f(x))にすると、関数を中身に出来るからもっと大きくなるってやつですね(詳しくは当該記事中編を参照)。今回は大きくなることより「関数が中身になる」方に着目している感じです。

forとwhile

　さて、「再帰」が何かある程度わかったところでちょっと話をプログラム言語に持っていきます。私はどれか選べと言われたら、どちらかというとC言語(実際はC++)に多少慣れているので、見出しの「for」と「while」でお話しさせてください。ただプログラムの中身の話はそんなにしません。あくまで機能の話(しかもイメージ重視)でとどめさせてください。
forというのは、C言語の世界では「回数を決めて繰り返す」プログラムです。一方whileは「条件を決めて繰り返す」プログラム。この違いをデュエマでやるならforは「《未来設計図》で山札を1枚ずつめくる動作」、whileは「《ヒラメキ・プログラム》で山札を1枚ずつめくる動作」をイメージしてくれると良いかなと思います。因みに、前段の例えに出した再帰の例はその殆どはforだけでもwhileだけでも大体作れて、こういうものを「原始再帰」と呼びます。現実世界における再帰は大体これ。なのですが、「原始再帰」で表せないぐらいヤバい再帰が世の中には存在したのです。

帰納的関数

　このもっとヤバい再帰、「帰納的関数」「μ再帰」なんて言い方をされるのですが、こちらはプログラムで考えると、forでは一部が作れず(原始再帰関数は帰納的関数の中の1分類)、それらはwhileでしか作ることができない代物となっています。ただ、「何が出来るのか」を説明するのがかなり難しいため、かなり話せる内容が絞られます。精度も割と死にます。「少なくともここに書いてあることが出来る、もっとすごいこともできる、それは普通にやるような再帰(=原始再帰)では作れない」というイメージだけ持ってほしいなと。
　まず、forは「(正しい文章で書いたとき)無限ループが作れない」ということが言えます。と、いうのも回数を決めて繰り返す都合、「何回やるか」を宣言しなければならず、デュエマでもそうですが、数学の世界も「無限回繰り返す」って宣言は基本的に許されません(イメージとしては、「無限」は数じゃない+回数には数しか入らない=「無限回」は存在しない)。ところがwhileだと「条件」を定めるので、「プログラムが動いていたら実行する」と書いて実行するだけで、雑に「無限に動くプログラム」が作れてしまいます。例えば山札が無限にあっても《未来設計図》は6枚しかめくりませんが、《ヒラメキ・プログラム》はクリーチャーが山札にいなければいつまでも山札をめくってしまうのです。で、この「時と場合によっては無限に終わらない」というのが計算世界では滅茶苦茶重要で、なんとチューリングマシンの材料の一端を担うだけの能力があります。
　チューリングマシンというのは、簡単に言えばアラン・チューリングという数学者が思いついた「なんでも計算できるマシン」です。ただ、この「なんでも」の部分に重大な瑕疵があり、「『チューリングマシンは何でも計算できるか？』という問題を計算で解いて」と命令すると、無限に計算を続けてしまって終わらなくなります。「できる」も「できない」も返せません。止まってないから計算自体は(今のところ)できていて、矛盾もしてません。ヤバいです。詰みです。が、この状態は逆に言えば「チューリングマシンと呼べるものは、特定の条件で無限に計算し続けないといけない」とも言えます。この無限に計算し続ける動作が、while、ひいては帰納的関数の持つ威力の一端と言えるでしょう。

《絶望神サガ》の計算能力

さて、whileのヤバさを大体ご理解いただいたところで、絶望神サガのテキストを見ていきたいと思います。

テキスト中の必要部分だけ抜き出すとこんな感じ。

■このクリーチャーが出た時、または自分のターンのはじめに、カードを1枚引き、自分の手札を1枚捨てる。その後、自分の墓地にクリーチャーが3体以上あれば、コスト5以下のゴッドまたはコスト5以下のオリジンを1体、自分の墓地から出してもよい。そうしたら、このクリーチャーを破壊する。

このテキストがコスト3のゴッドから出る、というと、DMPなら大体の人がヤバそうだな、と思うところですが、先ほどのwhileの話と一緒に考えると、このカードは「条件だけ(出た時)を指示して」「次の計算資源(サガ)を用意し(自己の破壊)つつ」「次の計算を直接呼びだす(場に出す)」という帰納的関数にやって欲しいこと全部が、物凄く綺麗に１文にまとまっているというプログラマ垂涎の品となっております。その上で「カードを1枚引いて手札を１枚捨てる」という「外部出力」まで完備。たった1枚のカードがC言語のwhile文プログラムとほぼ等価、グジェゴルチク博士(再帰のレベル分けをした偉い数学者)もビックリするでしょう。流石にこのカードだけでは不可能ですが、単独でwhileの能力を持つこのカードは、もし実験的手順でチューリングマシンを実装する時には、構成部品の一端として活躍することでしょう。

おわりに

　如何だったでしょうか(テンプレ)。ヤバいヤバいと言いつつ、所詮はカードゲーム上の存在、数学の目線で見たらただの子供用のオモチャかと思いきや、とてつもない威力を秘めた爆弾であることが、多少なりともわかっていただけたかと思います。本当は再帰関数とかチューリングマシンのネタとかもやりたいのですが、他にも執筆したいネタもありますし、今回はここまでにしようかなと思います。
　ご注意ですが、この記事は一定の専門家の指導の下、最低限嘘は無いように構成していますが、イメージのしやすさを優先しているため、話の精度については大幅に保証しかねる(特に帰納的関数って語の取り扱いとか結構怪しいです)部分もあります。もし誤りなどありましたら、コメントまたは私のTwitterなどにご意見いただければ幸いです。
　最後になりますが、もしこの記事を楽しんで頂けましたら、スキ機能、ブックマーク、Twitterフォローなどなど、よろしくお願いいたします。