コンピュータ理工学部 インテリジェントシステム学科 小林　聡 教授

神様のコンピュータは止まらない？

　背理法による証明はみなさんよくご存知だと思います。「Aではないと仮定すると矛盾が導かれる。よってAである。証明終わり。」この証明方法を学んだとき、疑問を抱いた人はどのくらいいるでしょうか？「なんだか、屁理屈みたいだ」「これで本当に“Aである”を証明したことになるのか」といった疑問です。このような疑問は決しておかしなものではありません。実は、数学とコンピュータ科学の世界もこの問題に悩まされてきました。コンピュータの行う計算を数学という基礎から研究されている小林聡先生にコンピュータが抱える計算の問題についてお聞きしました。

華やかな数学の発展の陰にコンピュータ科学への暗雲

　おおよそ19世紀まで、数学と言えば存在する解を求める学問でした。解が具体的に求まることが、問題が解けたということであり、具体的な解が分からないのであれば、それはまだ解けていないということだったのです。

　ところが、19世紀も半ばを過ぎると、代数学などの分野の高度化によって、具体的な計算によって証明を行うことがしばしば非常に困難となりました。そこで、「具体的な解は分からないが、ただ解が存在することだけを証明する」というアプローチが取られるようになり、「存在しないと仮定すると矛盾するから存在する」という背理法が脚光を浴びることとなりました。背理法では「解は存在するか存在しないかのいずれか」であること（これは「Aまたはnot A」という排中律の一つの形です）が前提となります。これは、解が存在するか否かは人間には分からないけれど神様なら知っているという「神様の視点」を数学に持たせた証明方法とも言えます。このことは数学の世界を大きく広げたと同時に、解を計算できるかどうかは問わない、といういわば「ツケ」を後のコンピュータ科学に残すことになったのです。

1900年に訪れた転機 ―― 計算可能とは？

　解を具体的に計算で求められないことが問題となる転機は、ドイツの数学者・ヒルベルト（ David Hilbert、1862〜1943）が提示した「ヒルベルトの23の問題」がもたらしました。1900年の国際数学者会議において、20世紀に取り組まれるべき数学の問題として世界中の数学者に示されたものですが、その中に「整係数多変数高次不定方程式※が整数解を持つかどうかを決定する一般的な解法を求めよ」という問題（ 第10問題）がありました。現代風に言うと「整係数多変数高次不定方程式が整数解を持つかどうかを判定するアルゴリズムを示せ」という意味であり、当時あいまいであったアルゴリズムという概念について数学者が考えるきっかけになりました。

　そのような判定は非常に困難であるため、多くの数学者が「そんなアルゴリズムはないだろう」という予想に傾いて行きましたが、「ない」と証明によって示すためには、アルゴリズムとは何か、つまり、計算できる範囲とはどこまでか、をはっきりさせる必要がありました。

　第10 問題が最終的に解決されたのは1970年のことですが、それまでに色々な数学者が計算とは何かを示しました。その中でも、現代のコンピュータ科学に大きな影響を与えたのは、イギリスの数学者・チューリング（ Alan MathisonTuring、1912〜1954）が考案した「チューリングマシン」です。

止まらない計算

　チューリングマシンは、無限の長さのテープ（ 記憶領域）とテープ読み取りヘッドから構成される仮想の計算機械です。みなさんが使っている、現代のノイマン型コンピュータはこのチューリングマシンと論理的に等価なのですが、そのような装置をコンピュータが発明される10年近く前に考え出していたわけです。

　チューリングはあらゆるアルゴリズムがチューリングマシンで実行できることを示したのと同時に、チューリングマシンには理論的限界があることも示しました。それは、チューリングマシンの計算が止まるか止まらないかを前もって判定するアルゴリズムはない（チューリングマシンの停止問題）というものでした。

　勘の良い読者の方はお気づきかもしれませんが、チューリングマシンが現代のコンピュータと等価ということは、現代のコンピュータにもチューリングマシンと同じ理論的限界がある、ということです。つまりプログラムが止まらないと計算結果が出なくて困ることがあるわけですが、止まるか止まらないかを事前に判断することは残念ながらできません。判断できる場合も多いのですが、どんなプログラムにも通用するような万能な判定法はありません。

　　「止まるかどうかは実際に動かしてみればわかるだろう」と思われるかも知れません。しかし、「止まる」が正しい答の場合は待っていればそのうち本当に止まりますけれど、「止まらない」が正しい場合は、いつまで経ってもわかりません。たとえ1時間計算して止まらなかったからといって、終わりのない計算をしているとは言い切れません。もしかするとあと10分計算させると止まるかもしれないのです。同じように10日止まらなかったものが11日目には止まるかもしれません。1年間止まらなかったものも1年と1日目に止まるかもしれません。

　神様の視点に立てば、「A または not A」という排中律は明らかですから、コンピュータは「止まるか止まらないかのいずれか」です。しかし、実際の計算となると「止まってみてはじめて止まると分かる」というケースがあり、「止まるか止まらないかのいずれか」などというのは計算する側にとって気休めにしかなりません。神様にしか分からないことはコンピュータにも分からないのです。

　さきほどの第10問題でいいますと、方程式に整数解があるかどうかを判定しようとして、整数解を探し続けるようなプログラムを作ることは簡単です。しかし、本当に解があった場合はいつか解が求まりプログラムが停止するのに対し、解がなかった場合にはプログラムがいつまでも止まらなくなります。そして、止まらなくなるかどうかを確実に判定する方法はないのです。

　さて、「プログラムが停止するなら1を、停止しないなら0を答えよ」という問題を考えます。神様の立場では（つまり排中律を使えば）この問題には解があり、それは1か0かに決まっています。しかし、実際に1なのか0なのかは一般に求められません。このように、神様の立場では解の存在は分かるけれども解を求める方法はない、ということが起こります。しかもこれは一例にすぎず、20世紀以降の数学にはそのような例が山のようにあります。

コンピュータが間違えたっていいじゃないか

　「解の存在は証明できるが、求め方は分からない」という状況はコンピュータ科学の立場からは不満です。そのような証明を避けたければ一般に排中律の使用を避けなければなりません。排中律と同等の原理である背理法もそうです。そのような論法を避けて、解の存在が証明できたらその計算方法も必ずわかるような形で数学を展開してみよう、という考え方で展開される数学を「構成的数学」と呼んでおり、私の研究テーマの一つです。

　19世紀までの数学は基本的に構成的数学で展開でき、それ以降の定理についても、証明をやり直したり、定理の記述を少し修正することで排中律を避けることは案外うまく行きます。20世紀の数学が解の計算方法を問わなくなったといっても、実際にはちょっと工夫すれば計算に応用できる研究成果が多いのです。

　しかし、排中律や背理法の一般形を使った途端、我々は「プログラムが止まらず、計算結果を出せない」という問題に阻まれます。定理の解をコンピュータに計算させたければ、排中律の使用はどうしてもあきらめなければならないのでしょうか?

　　私は現在、この問題にも取り組んでいて、ひとつのモデルを考えています。それは、非常に弱いバージョンの排中律を認める代りに、「コンピュータが間違える」ことも許す、というものです。正しい答を出そうとして永遠に計算を続けて黙りこくってしまう代りに、このモデルでは「最初のうちは間違えても良いからとりあえず答を出す」ことが許されます。しかし、間違いを放っておくわけではなく、プログラムは一種の学習を続け、間違いに気づいたら他の解を出します。それも間違っていたらまた別の解を出す、ということをくり返し、そうして学習を続けるうちにいつかは正しい解を出します。ただ、それがいつになるかは一般に保証できないのですが。

　これは科学の仮説と実証との関係をイメージすると分かりやすいと思います。科学では一般的な法則を仮説として研究を進めます。しかし、実験によって仮説の誤りが見つかることがあります。例えばニュートン力学はずっとうまく実験結果を説明できていたのですが、近代の実験で誤りが見つかり、相対性理論などで置き換えられました。相対性理論が否定されるかも知れない、という実験結果が最近発表されていましたが、確実に否定されるまでは正しい理論として用いられます。将来完全に誤りのない物理法則が発見されるかも知れませんが、「決して誤りがないこと」を確認する方法はないので、「間違いはあり得る」と考え続けながら科学は続いて行きます。しかし、間違いを恐れて永遠に黙っているよりも、間違いを正しながらの進歩のほうが科学にはふさわしいでしょう。

　一点だけ違う点をあげるなら、我々の計算モデルでは、「いつかは正しい答を出すことがある意味で保証されている」ということです。誤りが適切に指摘される限り、いつかは学習が成功して正しい答を出すような計算の仕組みを与えることができます。

　数学的には「極限計算可能数学」と呼ばれる考え方で、1回の試行で解を求めようとする普通の方法では計算可能でなくても、無限に学習を続けて誤りを正し続けて行く中でいつかは正しい答を出す、いわば極限においては正しい答を出せるという計算の数学なのです。

　コンピュータがこのタイプの計算を実行する様子を分かりやすくするために、人間が間違いを指摘するゲームを試作しました。コンピュータは問題の解を正しく出せば勝ちで、人間はコンピュータの「思考過程」の間違いを指摘できれば勝ちです。最初のうちコンピュータは間違えて負けることがありますが、負けたあとゲームをやり直すと前より賢くなっています。人間側が勝とうとして厳しく間違いを指摘してやるほどコンピュータ側は賢くなり、コンピュータは試行錯誤しながら正解へと近づいて行くゲームです。ゲーム仕立てにすることで間違いが正されていく過程を観察することができ、極限計算可能数学の理解を助けてくれます。

　優秀な創造力を持つ人間の脳はよく間違えます。コンピュータにも間違いを許容することで新たな計算への可能性が開けてくるかもしれません。

排中律はほんとうに正しい？　ブラウワーの反例

　排中律の無制限の使用に反対した数学者として有名なのがオランダのブラウワー（Luitzen Egbertus Jan Brouwer、1881〜1966）です。彼は、排中律への批判として「円周率に0が100個並ぶ場所がないかどうかどうやって分かるのか」という例を挙げました。円周率は終わりなく数字が並ぶ無理数です。計算を続けていけばもしかしたらいずれ0が100個並ぶ場所が出てくるかもしれません。でも、それは今のところ誰にも分かりません。確かめるためには計算を延々と続けなければなりませんが、出てこなければいつまでも計算が終わらず、まさに停止しない計算になってしまいます。このような考え方から、ブラウワーは「排中律を無条件に使うべきではない」と主張しました。このような主張は当時論議を呼びましたが、ブラウワーの思想は今日の構成的数学を生み、コンピュータ科学へ大いに寄与しました。