10分で分かるゲーデルの不完全性定理 ～ いまさら聞けないコンピュータサイエンス【連載第１話】
「我々は知らねばならず、そして知るであろう」
ドイツが生んだ大数学者であり、「現代数学の父」と呼ばれた天才ダフィット・ヒルベルトは、このスローガンをかかげて世界の数学者を激励しました。
ドイツが第一次世界大戦とベルサイユ条約による打撃から回復し、ヨーロッパにナチスの足音が聞こえ始めた1930年（昭和５年）に、すでに晩年にあったヒルベルトによるこのスローガンから、コンピュータサイエンスの壮大なドラマが始まります。
１．数学者に禅問答を課した「ヒルベルト・プログラム」
時は遡ること19世紀最後の1900年（明治33年）、ヒルベルトは「20世紀で解決されるべき重要な未解決問題」を発表しました。これが「ヒルベルト・プログラム」です。
これには、次の2つの難題が含まれていました。
・数学は宇宙を完璧に記述できることを証明せよ
・食卓に出されたスパゲティがうまいかまずいかを食べる前に決定せよ
……もちろん、これはヒルベルトが出した問題を極端に易しく言い換えた表現ですが、趣旨としてはだいたいこんな感じです（分かりやすさを優先して厳密性を犠牲にしているので、数学的に正確なことを知りたい人は専門書を読んでください）。
ほとんど禅問答であり、即座に「無理！」と匙を投げたいところですが、数学の万能性を信じたピュアな大数学者は、いずれも「できる」と予想していました。
しかし、前者はクルト・ゲーデルによって、後者はアラン・マシスン・チューリングによって、いずれも「できない」と数学的に証明されました。禅問答を出題するヒルベルトも、これを解いてしまう２人も、「まさに天才」を体現したような人々です。
そして、チューリングが後者の問題を否定的に解決する過程で生み出した「チューリング・マシン」と呼ばれる概念が、現代のコンピュータサイエンスの基礎になっています。
また、この２つの禅問答は相互に深く関連しているため、チューリング・マシンの概念を理解するためには、まずはゲーデルが解いた前者の問題を理解する必要があります。
そのため、連載最初の記事ではこれを説明したいと思います。
２．数学の危機を招いたパラドクス
そもそも、なぜヒルベルトはこんな無理難題を発表するに至ったのでしょうか？それは、当時の数学界において、数学の万能性を疑問視する不安の声が高まっていたからです。
きっかけは、数学の基礎的な部分を研究する「数理論理学」と呼ばれる学問分野で、些細なパラドクス（矛盾）がいくつか発見されたことでした。なかでも、次のパラドクスは有名です。
「床屋は、自分でひげを剃らない人のひげを剃り、自分でひげを剃る人のひげは剃らない。さて、床屋は自分自身のひげを自分で剃るのか？」
床屋は「自分でひげを剃らない人のひげを剃る」のですから、自分で自分のひげを剃らないなら、自分で自分のひげを剃ることになる……これは矛盾です。
逆に、「自分でひげを剃る人のひげは剃らない」のですから、自分で自分のひげを剃るなら、自分のひげは剃らないことになる……これも矛盾です。
……もちろん、床屋の比喩は、数学の議論を易しく言い換えた表現です。「床屋は自分自身のひげを自分で剃るのか？」という命題（数学的に意味のある文章）は、数学的な記号とその操作からなる抽象的な「論理」として実際は表現されます。
しかし、この命題に対して「剃る」とも「剃らない」とも言えてしまう矛盾に陥ることは同じです。
数学では、命題に対して「正しい（真）」と結論づけることを「証明」と呼び、「誤っている（偽）」と結論づけることを「反証」と呼びますが、ある種の命題に対しては「証明も反証もできてしまう」ことがパラドクスの存在によって明らかになったのです。これはまずい。
なぜまずいのか？
もちろん、数学の万能性が怪しくなるからです。「証明も反証もできてしまう」ということは「結局何が真実かが分からない」ということですから。
人間の理性を働かせれば、この世のあらゆる事象を「数学」という共通言語で客観的に記述できることを、全員が信じていたはず。
しかし、数学には限界があるかもしれない……もしそうなら、「どういう条件のもとで何がどこまでできるか」の限界はどこにあるだろうか……世界の数学者たちはこう不安になったのでした。
これに対して、当時すでに数学界の大御所であったヒルベルトは、「皆、落ち着け、数学はあらゆる意味で万能に違いない。我々がそれを証明しようではないか！」と叱咤し、「数学は宇宙を（矛盾なく）完璧に記述できることを証明せよ」という第一の禅問答を出したわけです。
３．ヒルベルトが期待した「完全かつ無矛盾」
ヒルベルトの禅問答をもう少し数学的に表現すると、「数学の体系が完全かつ無矛盾であることを証明せよ」になります。禅問答よりはマシになりましたが、まだ意味が分かりません。
数学では「公理」を設定して議論の舞台を整えるところから出発します。公理は「問答無用で『正しい』こと」です。何かが正しいと共通認識を持たなければ何も議論が始まらないので、まずは「いま前提として何が正しいか」を決めてしまいましょうということです。
例えば、最も素朴には「同じものに等しいものは、互いに等しい」とか「同じものに同じものを加えた場合、その合計は等しい」とか、直感的に当然と考えられることを公理として設定できます。
公理を設定した後は、その公理を土台にして、公理系（一連の公理によって規定される抽象的な議論の枠組み）に存在する命題の「証明」または「反証」を試み、それぞれの真偽を確定させていきます。
そして、ヒルベルトは「公理系に含まれるすべての命題は証明または反証できる」ことを期待しました。これを「完全」と呼びます。逆に、証明も反証もできない命題が存在する場合を「不完全」と呼びます。
不完全であることは、公理が足りないことを意味します。説明できないことがあるのは、そもそも前提が足りないのです。それなら、とっとと公理を追加すればいい。そうすれば、表現力が上がって証明・反証できるようになります。
ただし、公理を追加した結果、命題の真偽が非整合になることは避けなければなりません。つまり、必要以上に公理を追加して余分に表現力を上げてしまうと、ある命題の証明も反証も両方できてしまうおそれが生じます。
これを「矛盾」と呼びます。ヒルベルトはこれを嫌って「公理系は無矛盾である」ことを要求しました。
まとめると、ヒルベルトが理論的に明らかにしたいと考えたことは「必要十分な公理を慎重に設定すれば、数学の体系は完全かつ無矛盾となること」でした。
言い換えれば、完璧な公理系では、証明できるなら真が、証明できない（反証できる）なら偽が、すべての命題で一意に対応し（完全）、これ意外はあり得ない（無矛盾）ということです。
これさえ明らかになれば、数学の万能性は揺るぎません。公理系がどれほど大きく複雑になろうとも、矛盾なくすべての命題が必ず証明または反証できると保証されるからです。
そして、これが保証されれば、いつの日か、数学は宇宙ののすべてを記述し尽くすことができるだろう。いまはまだそこまで達していないけれども、皆で坂の上の雲を目指そうではないか！！
ガリレオ・ガリレイは「自然という書物は数学という言葉で書かれている」と言いましたし、デカルトは「数学で認識することが現実と一致することには神の保証がある」と言いました。
ヒルベルトは、ルネサンスの時代から脈々と受け継がれてきた数学と自然科学に対するこの信仰を守ろうとしたのかもしれません。
こうして、数学の天才はスローガンを掲げ、その万能性を期待して世界中の数学者に呼びかけたのでした。
４．数学の万能性を打ち砕いた「不完全性定理」
ところが、ヒルベルトのこの期待を吹き飛ばした数学者が現れました。未曾有の天才クルト・ゲーデルです。
当時24歳の若きゲーデルは、「公理系の表現力が一定以上となった場合、『完全』と『無矛盾』は両立しない」ということを証明しました。これを「第一不完全性定理」と呼びます。
公理系に含まれる正しい命題はすべて証明できてほしいし、正しい命題から正しい手順を踏んで推論する限り、それは無矛盾であってほしい……先に説明したとおり、ヒルベルトは完璧な数学を期待したのですが、残念ながら、理論的にそうではありませんでした。
もちろん、両立する場合もあります。しかし、それは限られた表現力を持つ体系のみです。ヒルベルトが期待した十分に表現力の高いリッチな体系では、どうがんばっても両立しないことが明らかになりました。
具体的には、ゲーデルは「ゲーデル数」と呼ばれる独自の概念を用いて、「この命題は証明できない」という自己言及を含む命題を作ってみせ、これが真であれば証明不可能で、証明可能なら偽となる矛盾を導いたのでした。これは、先の「床屋のパラドクス」と広い概念的としてほとんど同じです。
また、ゲーデルは「ある条件を満たす公理系は、それが無矛盾である場合、その公理系において、それ自身が無矛盾であることを証明できない」ことも証明しました。これを「第二不完全性定理」と呼びます。
自分の正しさを自分自身では証明できないことは直感的に当たり前のことなのですが、ゲーデルは、第一不完全性定理で存在が示される「証明も反証もできない命題」の一例が、 自分自身の無矛盾性を表す命題であることを証明しました。
これが「ゲーデルの不完全性定理」のざっくりとした（あくまでざっくりとした！）説明です。
※この明晰な定理を文章のみで正確に説明するのは基本的に無理筋なので、腕に覚えがある人は数式盛りだくさんの専門書を読んで正確に理解することをお勧めします。
この定理は「数理論理学」における議論の土台を不安定にし、数学の万能性を部分的に打ち砕いた伝説の定理となりました。
＊＊＊
冒頭のように、ヒルベルトは、1930年に故郷ケーニヒスベルクで開催された国際会議の招待講演でスローガンをかかげ、次のように世界の数学者を激励します。
我々にとって不可知論はあり得ないし、自然科学全体にとってもこれは全くあり得ないことであると確信する。ナンセンスな不可知論とは正反対に、我々の合言葉は次のようなものである。『我々は知らねばならず、そして知るであろう』
これはドイツの生理学者レーモンによる「我々は知らない、また知ることもないであろう」という不可知論（「人間の認識には限界がある」と考える哲学思想）に対する批判でした。
つまり、「ある種の科学上の問題について、人間はその答えを永遠に得られないだろう」と述べたレーモンに対して、「数学を基礎にした自然科学は、あらゆる答えを得ることができる」と、ヒルベルトは反論したのです。
ところが、皮肉なことに、同じ国際会議でゲーデルが不完全性定理の概要を発表していました。しかも、招待講演の前日に！ヒルベルトは招待講演の準備で忙しく、幸か不幸か、ゲーデルの発表を聞いていなかったそうです。
代わりに、弟子のジョン・フォン＝ノイマンが発表を聞き、数学界に与えるそのインパクトを直ちに理解しました。そして、ノイマンは発表を終えたゲーデルに「後で詳しく教えてほしい」と耳打ちし、師匠が招待講演を終えた後に、衝撃的な発表の内容を報告したそうです。
翌1931年（昭和６年）に、国際会議での発表をまとめたゲーデルの論文が出版されます。このときヒルベルトは68歳。世界の数学界に君臨する重鎮です。25歳の若者が書いた論文を一読し、すぐさま内容を理解した天才は、笑っているような、怒っているような、不思議な表情を浮かべたと伝えられています。
数学の万能性を確信していたヒルベルトは、もちろんガッカリしたでしょう。世界の数学者も、後に「ゲーデル・ショック」と呼ばれるほど驚愕しました。
「数学的な論理を突き詰めていけば、どんな命題についても真偽の判定ができ、それを延々と積み重ねていけば、いつかは神の真理に辿り着ける」…ピュアな信仰が脆くも崩れ去ったわけですから。「数学は思っていたほど万能ではなかった」と。
しかし、同時にほっとしました。なぜなら、「どういう条件で何がどこまでできるか」の限界が明らかになったからです。数学を含む自然科学では、「ここから先はできない」という限界が明らかになり、それを前提としてさらに多くの成果を生み出すきっかけになることが多いのです。
そのため、ゲーデルの不完全性定理は科学を挫折させるものでは決してなく、むしろ、数学の新たな出発点として、人類が獲得した進歩と言えるでしょう。そして……その新たな出発点から大きな一歩を踏み出したのが、そう、それがまさに、「コンピュータサイエンス」だったのです。
５．ヒルベルトとゲーデルの晩年
1933年（昭和８年）に、ナチスはドイツの大学に対して、教職からすべてのユダヤ人を追放することを命じました。
これは、ドイツ国内の才能を叩きつぶす最悪の布告で、ヒルベルトが教授職に就いていたゲッティンゲン大学にも壊滅的な影響がありました。
当時、世界の数学の中心はヒルベルト一派が牽引するゲッティンゲン大学でした。しかし、ユダヤ人だった彼の弟子たちが迫害を逃れてドイツを離れたために没落してしまったのです。
例えば、20世紀を代表する数学者では、クーラント、ワイル、ベルナイス……そして、国際会議でゲーデルの発表を聞き、後に近代コンピュータを生み出すことになるノイマンがいました。結局全員がアメリカに亡命し、プリンストン高等研究所に移ってしまいました。
ナチスの役人がゲッティンゲン大学の数学研究所の所長になると、それまで週１時間の数学基礎論の講義をしていたヒルベルトは、二度と研究所に顔を出しませんでした。
そして、1943年（昭和18年）２月、ヨーロッパ全土で第二次世界大戦が激化するなかで、大数学者ヒルベルトは82歳で亡くなりました。彼の墓碑には、今もこう刻まれています。
「我々は知らねばならず、そして知るであろう」
＊＊＊
時は遡って1938年（昭和13年）、ドイツがオーストリアを併合したため、オーストリアは「ドイツ国内」と同じ扱いになります。
ゲーデル自身はユダヤ人ではありませんでしたが、ドイツがポーランドに侵攻して第二次世界大戦が勃発すると、ドイツ軍に招集されかねない事態に陥りました。
戦争が激化するにつれてウィーンはどんどん物騒になり、あるときゲーデルはナチズムを信奉する学生に襲われます。これにより、ついにオーストリアを出国してアメリカに向かう決意を固めたのでした。
ノイマンの手引きでドイツ出国許可証とアメリカの特殊ビザを入手したゲーデルは、ドイツ海軍に封鎖された大西洋を避けてリトアニアからラトビアを経由し、シベリア鉄道でソ連を横断し、さらに横浜から太平洋を横断する汽船でアメリカに渡りました。
華の都ウィーンを追われ、凍てついたシベリアの大地を車窓から眺める彼の心境は、いかばかりだったでしょうか。言葉も通じない異国の地を転々としながら、ほとんど地球を一周する長い旅程のなかで、若き天才の心も凍てついたに違いありません。
アメリカに着くと、ゲーデルはノイマンからプリンストン高等研究所に招かれました。当時の研究所は、アインシュタイン、ノイマン、ゲーデルなど、世界中の天才が集まる世界一の研究機関となり、ゲッティンゲン大学に代わって数学・物理学の聖地になったのです。
彼は研究所でアインシュタインと親しく付き合います。アインシュタインは、「散歩しながらゲーデルと議論する時間が楽しくて仕方ない」と述べています。
しかし、アインシュタインが亡くなると、もともと社交的でなかったゲーデルはふさぎがちになり、晩年には精神に異常をきたしてしまいました。
そして、ついに絶食による飢餓状態に陥っているところを発見され、すぐに病院に搬送されましたが、1978年（昭和53年）、プリンストン病院で亡くなりました。このとき、ゲーデルの体重は、170センチの身長に対して約30キロしかなかったそうです。
＊＊＊
次回は、コンピュータサイエンスを作り上げ、波瀾万丈の人生を送った天才チューリングの物語です。
「食卓のスパゲティがうまいかまずいかを食べる前に決定せよ」というヒルベルトの無茶ぶりを、チューリングがどのように解決したのか！？
不完全性定理で新たな出発点が示され、そこから踏み出した大きな一歩がコンピュータサイエンスであるとは、いったいどういうことか！？
待て！次回！
====
・この記事を書いた藤田の連絡先は、こちら。