研究者な俺と幼馴染が紡ぐイチャイチャ研究生活

第6章 文化祭に向けて

第35話 決定不能問題

　さて、一応、一線を超えた俺と涼子だけど。

　しかし、だからと言って大きく何が変わるわけでもなく、

　翌週の月曜日を迎えたのだった。

　ただ、登校時に隣を歩く涼子が心無しか晴れやかな表情だ。

「なあ、涼子」

「！？どうしたの？」

　慌てて、今気づいたという素振りだ。

「いや、それはこっちの台詞だけど。文化祭の事で、ちょっと」

「あ、そういうこと。てっきり変なこと言ってくるのかと……」

「へ、変なことって何だよ」

「……エッチ」

「いやいや、待て待て。俺は普通に話題振っただけだろ。なんで、エッチ！？」

　なんとなく、こいつが考えていたことも想像がつくけど。

「言っておくけど」

「けど？」

「その……エッチなことはいいけど。あまりがっつくのは止めてよね」

「がっつくとかなんとか。研究に集中し過ぎて仲が進まなかったくらいだろ」

　だから、不要な心配だと思うのだが。

「だって。私は、嫌じゃなかったし。なんか、続くとハマっちゃいそうだし」

「ま、まあ。俺も嬉しかったけど。別に、研究放置なんてことにはならんだろ」

「そ、そうね」

「だから、考え過ぎだって」

　とはいえ、涼子の言うことも少しはわかる。

　デートも含めていちゃつく事は重要だけど、俺達の目指すのは研究者への道。

　というより、もはや半分以上研究者なのだ。

　節度を守ろうということだろう。

「ま、でもさ、研究に集中し過ぎた時の息抜きにはちょうどいいと思うんだよ」

　今まで、俺達は、そちらに全力を振り過ぎていたように思う。

「確かに、息抜きと考えれば、いいことかもしれないわね」

「そうそう。息抜き、息抜き」

　ということで、朝の一幕は過ぎて、放課後、マイコン部にて。

「文化祭の話だけどさ。「決定不能問題」の話、入れられないか？」

　少し、朝考えていたアイデアについて提案する。

「「決定不能問題」の話は、それこそ、一般の人には難解じゃないかしら」

「しかし、そもそも、「コンピュータとは何ぞや」の話には欠かせないだろ」

「言いたいこともわかるけど」

「それに、ある意味、マイコン部らしい話に出来ると思うし」

　と議論をしていたところ、

「「決定不能問題」って何ですか？なんか、小難しそうですけど」

　話に割り込んできたのは、後輩の結菜（ゆな）だ。

「一言で言うと、「コンピュータには絶対に解けない問題」の事だな」

　凄まじくざっくりした説明をする。

「たとえば、小説はコンピュータには書けないとかそんなのですか？」

「いや、そっちは、むしろ、原理的には「書ける」問題の方に入る」

「でも、PCが勝手に小説を書き出す様子は想像出来ませんけど」

「さすがに、現在の技術だとまだまだだな。ただ、不可能な問題じゃない」

「最近流行りのAIだと出来るって奴ですか？」

「AIは専門外だけど、いつか、AIで人間並の小説が書ける日も来るかもな」

「だとしたら、コンピュータだと絶対解けない問題っていうのは、一体？」

　確かに、AIが発展したら、何でも出来るようになる、

　という論調は最近よく出てくる。しかし、そうではないのだ。

「そうだな。たとえば、全自動プログラム暴走発見機、なんかが典型だろうな」

「それは、今だと確かに無理ですけど、それこそいずれAIが解決してくれそうな？」

　確かに、結菜にとっては、どちらも似たように見えるだろう。

「じゃあ、手っ取り早く、全自動でプログラムが暴走するかを判定するプログラムが書けないことを証明してみよう」

　カカっと書き出す。

function mustBeCrash(program, input) {

　　// プログラム本体

}

「こんな、mustBeCrash関数がもし定義出来たと仮定する。programはJavaScriptの文字列で、inputは入力だな。programをinputを与えて走らせた時に、暴走する、つまり無限ループするなら、trueを、暴走しない、つまり、ちゃんと終了するなら、falseを返すことにする」

　典型的な、背理法による証明だ。

「mustBeCrash関数が定義出来たら嬉しいな、って事ですよね」

「で、仮にmustBeCrash関数が存在すると、おかしなことが起きるんだ」

　このmustBeCrash関数を使った、おかしなプログラムの例を書いてみる。

function main(input) {

　　if(mustBeCrash(main, input)) {

　　　return

　　} else {

　　　while(true) {} // 無限ループ

　　}

｝

「で、このmainを実行するとだ。もし、main「それ自体」が「暴走する」とmustBeCrash関数が判定したら、returnして、正常に終了する。一方、mustBeCrash関数が「暴走しない」と判定したら、無限ループに入ってしまう。つまり、mainは、暴走すると判定されたら、暴走せず、暴走しないと判定されたら、暴走する」

「なんだか、話がこんがらがってきました」

「まあ、ややこしいよな。問題は、mustBeCrashなんて関数が書けると仮定したことにあるんだ。よって、mustBeCrash関数は書けない。ちょっと証明としては色々雑なんだが。そんなところだ」

「なんだか、狐につままれた気分です……」

　さすがに、これだけの証明だと納得出来ないらしい。

「まあ、とにかく、納得出来ないかもしれないが、あらゆるプログラムについて、無限ループしているかどうかを判定するプログラムというのは、絶対に書けない。これは未来永劫変わらない。数学で、1 + 1 == 2なのが絶対変わらないのと同じだな」

「専門家の先輩が言うんならそうかもしれません。でも、ふつーの人は、無限ループするかどうかチェックするアプリとか関係ありませんよね？」

「う。まあ、そうなんだが……」

　結局、そこが痛いところなのだ。

「そうね。結菜が一応わかりそうな実例だと、Javaコンパイラとかどうかしら」

「そういえば、数年前論文が出てたな。結菜もJavaは少し書けたよな」

「え、ええ。最低限ですが、一応」

　戸惑ったように答える結菜。

「で、Javaは型チェックをして、おかしいとエラーになるよな」

　と、間違っているプログラムの例として、

int x = "Hello";

　を書いてみる。

「整数型には、文字列は入りませんとか出そうですね」

「そうそう。Javaコンパイラはそういうチェックをするんだけど、Javaコンパイラが無限ループすると思うか？」

「さすがにそれは困りますよね。なんとなく、しない気がしますけど」

　一応、簡単でもプログラムを書いたことがあるとそう思うよな。

　よし、と手応えを感じる。

「実は、Javaコンパイラは無限ループする、ということを証明した論文が、2017に提出されたのよ」

　その論文のタイトルは、

　Radu Grigore. 2017. Java generics are turing complete. In Proceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages (POPL 2017).

（※実在の論文です）

「正確には、無限ループすること「も」あるってところだけどな」

「でも、それって、単にソフトがバグってたんじゃないんですか？」

　ああ、そうか。そうも聞こえるよな。

「実はそうじゃなくて、Java言語のコンパイラを忠実に実装すると、必ずどこかで無限ループが発生するということなんだ。そこがこの論文の面白いところでな」

　俺は型システムは専門外だが、知人の研究者に「これ、面白いよ」

　と紹介されたので読んだクチだ。

「うーん。わかったような、わからないような。じゃあ、Javaのコンパイラは、下手な書き方をしたら、永遠に終了しないんですか？」

「原理的にはな。実用的には、論文に書いてあるような例はなかなか作れないから心配しないでいいんだけど、とにかく、「必ず停止するような、プログラムをチェックするプログラム」が作れないという点では、さっきのmustBeCrashと同じ事なんだ」

　正確には、Javaの型システムに対する型チェッカーを構成出来ない、だけど。

　そこは説明すると泥沼なので、はしょる。

「まあ、こんな感じで、役に立つプログラムでも、数学的な限界のせいで、書けないプログラムがある。こういう、「書けないプログラム」の集まりを「決定不能問題」というんだけど、俺達の専門である、形式言語理論にも関係してくる。というのを、文化祭で盛り込めないかと思うんだけど、どうだ？」

　渾身のアイデアなのだけど。

「実は、私も、コンピュータに限界があるというのは初耳でした。そこだけうまいこと説明すれば、展示にはなる、気がします。ただ、展示には、さっきの小難しい説明を入れると見に来た人がチンプンカンプンになりますから、いい説明が必要ですね」

「よしっ」

　説明を工夫すればいけそう、と言ってもらえたのは収穫だ。

「でも、正直な話ですが、やっぱり地味ですね」

「ぐっ。そこを突かれると弱いな……」

「やっぱり、見栄えのするインタプリタを作るのがいいかしら」

「そういえば、涼子先輩が言語作るって話もありましたよね」

「ええ。と言っても、おもちゃみたいなものだけど」

「たぶんですけど、それでブロック崩しとか作った方が観客受けはいいですよ」

「わかる、わかるんだが。なんか、負けた気分だな……」

「仕方ないわよ。あなたの案も展示に入れるから」

　だから、落ち込まないで、とポンと肩を叩かれる。

「まあ、仕方ないよな。仕方ないんだ……」

　と、知らない人に研究を伝えることの難しさを噛み締めたのだった。