【第1話】ヒルベルト・プログラムとゲーデルの不完全性定理

このマガジンの第1話として、どうやって「計算機(コンピュータ)は生まれたのか」というところから書こうと思います。

チューリング・マシンが計算機科学の基礎理論

コンピュータの基礎理論は、すべて「チューリング・マシン」が土台になっています。チューリングは、イギリスが生んだ天才数学者です。チューリングと言えばコンピュータ、コンピュータと言えばチューリング。そして、実は「人工知能の父」もチューリングなのです(ミンスキー説もあるけど、個人的にはチューリングを推したい)。

ちなみに、第2次世界大戦時にドイツ軍の「エニグマ暗号」を解読した過程を描く映画「イミテーション・ゲーム」の主人公としても、チューリングは有名ですね(このタイトルの由来は後述)。この映画はめっちゃ面白いので、未視聴の方には絶対オススメです。予告編はこちら。以下は一部抜粋画像。

数学基礎論の混乱

さて、「チューリング・マシン」は、チューリングが考え出した「仮想計算機」です。つまり、数学的な理論上の計算機であって、実態のあるコンピュータではありません。では、なぜチューリングがこの仮想計算機を考える必要があったのか?……そもそもの経緯から知らなければ、カラクリが理解できないので、まずはここから説明しましょう。

19 世紀末の数学界は、混乱の渦中にありました。20 世紀を代表する知の巨匠ラッセルが、数学の基本的な部分に矛盾を発見したことが発端でした。一言で表現すると「数学ヤバくね?」です。

何がどうヤバいのか?……ちょっと「レンガ造りの大聖堂」を想像してみてください。

たくさんの数学者が二千年以上かけて、少しずつレンガを積み上げて大聖堂の完成(完璧な数学の構築)を目指してきたつもりだったんですが、よく見たらそれを支える一番土台の部分がグラついてることが分かってしまったわけです。

土台が崩れると、その上に積み上げたレンガもボロボロ崩れるかもしれない。しかも、どのレンガが崩れそうかも分からない……いままでの数学者の努力と成果が無に帰すのでは?……ラッセルが指摘したことはこれでした。

ヒルベルト・プログラムのはじまり

それに真っ向から立ち向かったのが、大数学者ヒルベルトです。彼は 19 世紀最後の年、1900 年に開かれた国際数学者会議で「数学が形式的に『完全かつ無矛盾』であることを示そう」と世界の数学者に呼びかけました。これを「ヒルベルト・プログラム」と呼びます。

言い換えれば「まずは土台を慎重に造り直そう。そして、機械的な手順でレンガを積めば、いつか必ず大聖堂が完成することを証明しようじゃないか」ってことです。

……はい、この時点ですでにブラウザのバックボタンを押しかけてる人が続出してると思うので、少年向けマンガの例を用いて易しく説明しようと思います。

少年向けマンガの王道は「主人公がパワーアップを繰り返し、ピンチを乗り越えながら次々と現れる強敵を倒し続ける」です。ドラゴンボールとかワンピースとか、全部このワンパターンを踏襲してますね。実に単純です。

ところが、少年向けマンガには「連載が続くにつれて敵の強さがエスカレートする」という宿命があります。にもかかわらず「主人公は必ず敵に勝つ」という結論は絶対に曲げられません。主人公が負けたら連載が終わっちゃうからです。当然ですね。

しかも、主人公が「普通に修行して強くなる」という王道のストーリーでは倒せないレベルの理不尽な敵を、ミスってたまに登場させちゃうことがあります。つまり「連載当初の世界観やキャラ設定だけでは勝てない」っていうムチャな展開になることがある。

「わたしの戦闘力は 530000 です」が、どれほど読者を絶望の淵に追い込んだことでしょう。編集者が人気マンガの連載を引っ張ったあげく、作者を煽りすぎた結果じゃなかろうか?……などと大人の事情に思いを馳せる瞬間です。

同じように、数学では「証明できない命題」(=絶対倒せない敵)が、その世界観に含まれる状態を「不完全」と呼びます。ヒルベルトは、まずこれを嫌って「数学は完全だ」(=倒せない敵など現れない)ということを示したいと考えました。

さて、うっかり理不尽な敵を登場させてしまった作者は、設定を後付けします。例えば「主人公には未知の能力が隠されていた」とか「これまで絶対不可能のはずだったスペシャル必殺技を身につけた」とか、そういうやつ。それでストーリーの行き詰まりを打開するわけですね。

ところが、今度はその場しのぎで後付けした設定が、マンガの世界観や前後のストーリーをおかしくすることがあります。いまそれがアリなら、前のあのピンチは何やねん!最初からそれやっとけや!みたいな、あの納得いかない感がそれです。「ドラゴンボール 矛盾」とかでググりましょう。

数学では、こんなふうにストーリーが行き詰まって命題の真偽が食い違う状態(証明の結果が「イエス」とも言えるし「ノー」とも言える奇妙な命題が存在する状態)を「矛盾」と呼びます。なので、ヒルベルトは「ストーリーは矛盾せず破綻しない」ことも示したいと考えました。

要するに、ヒルベルトが期待したことをまとめると「マンガの世界観やキャラなどを慎重に設定すれば、ストーリーが破綻することなく、どんな敵でも倒せるはずだ!」ということです。ものすごくざっくりした説明ですが、これが「完全かつ無矛盾」の意味です。

この「完全かつ無矛盾」が証明できさえすれば、土台がしっかりするので、そこへ機械的にレンガを積み上げ続ければ、いつか必ず大聖堂が完成することが保証されます。

ゲーデルの不完全性定理

ところが……賢明なる読者諸氏はすでにお気づきのとおり、この天才数学者ヒルベルトの期待を木っ端みじんに吹き飛ばした天才がいました。チェコ出身の数学者ゲーデルです。

彼は「完全と無矛盾は両立しない」というミもフタもないことを証明してしまいました。これが「不完全性定理」です。すでに数学界の大御所だった老ヒルベルトは大層ガッカリしたそうな。

これを少年向けマンガの例に置き換えると、次のとおりです。
(1)マンガの世界観を矛盾なく設定しても、絶対倒せない敵が現れてしまう
(2)マンガの世界観が無矛盾であるかどうかは、その世界観の中では確認できない

ここでは、とりあえず上記(1)の「作者がどうがんばっても、絶対倒せない敵(証明できない命題)の出現は避けられない」だけを理解できれば十分です。

ちなみに、ゲーデルは弱冠 24 歳でこの不完全性定理を証明しています。もう1つちなみに、チューリングも 24 歳で「チューリング・マシン」を考案しています。歴史に名を残す天才は、早熟なんですねぇ……。

チューリング・マシンで示された「計算」の概念

このゲーデルの不完全性定理を瞬時に理解した若き天才チューリングは「具体的にどんな命題が、どんな風に証明できないのか?」と疑問を持ちました。ゲーデルは「証明できない命題が存在する」(絶対倒せない敵が出現する)ということを明らかにしましたが、「証明できない命題の具体例」まで深掘りして明らかにできていなかったからです。

いまさらですが「証明できる」というのは「命題の真偽(イエスまたはノー)を判定できる」ということです。そして、チューリングが疑問を持ったことを言い換えると「『その命題を証明できるかどうか』を決定できない場合はあるか?あるとすれば、それはどんな場合か?」ということなので、この問題を「決定問題」と呼びます。

例えば「9-4は5か?」という命題に対しては「正しいと証明できる」と決定できます。なぜなら「9-4=5」と計算できるからです。同じように「323 の素因数は 17 と 19 か?」という命題に対しても「正しいと証明できる」と決定できます。いわゆる「素因数分解」で計算できるからです(中学校くらいで習いましたよね?)

では、どういう命題が証明(真偽を判定)でき、どういう命題が証明できないのでしょうか?
言い換えると、何が計算できて、何が計算できないのでしょうか?
もっと言えば「計算する」って結局どういうことなのでしょうか?

これがチューリングの立てた問いです。天才は問いのスケールがでかいですね。これは「計算の限界」を示すものですのであり、「計算可能性」と呼びます。

決定問題の否定的解決

で、チューリングが行き着いた答えは「チューリング・マシンが構成できるなら計算可能」ということでした……はい、また何のことやらサッパリ分かりません。そもそも「チューリング・マシン」って何やねんって話です。

……というわけで、チューリング・マシンを説明したいところなのですが、その説明を始めるとこのエントリーがクソ長くなるので、ここでは思いっきり端折ります次の記事に書きました)。とりあえず、チューリング・マシンを表すポンチ絵だけを出しましょう。

何じゃこれ?と思ったアナタ。安心してください。正しい反応です。もちろん、天才チューリングが数学の論文でこんなポンチ絵を描くはずありません。でも、チューリング・マシンの概念を絵にすると、本当にこんな感じになるんです。

ウソだと思ったら、チューリング・マシンで画像検索でもしてみてください。ほ~ら、似たような絵がたくさん出てくるでしょう。↓こんな感じで。

ざっくり言えば、チューリング・マシンとは「アルゴリズム」そのものです。そして「チューリング・マシンを構成できる」ということは「アルゴリズムが存在する(計算の手順が存在する)」ということです。なので、当然ながら「9-4=5」を計算するチューリング・マシンは存在します。「323 を素因数分解する」ためのチューリング・マシンも存在します。

ところが「『あるチューリング・マシンが結果を出して停止するかどうか?』を決定するチューリング・マシンは存在しない」ことを、チューリングは証明しました。これを「停止問題」と呼びます。つまり「停止問題を解くアルゴリズムは存在しない」(=計算できない)のです。

この時点で、チューリングは、ゲーデルの不完全性定理を裏付ける例題として、具体的に「停止問題」を発見したことになります。その上で、チューリングは「停止問題が証明できるかできないかは決定できない」を明らかにしました(※1)。なぜなら、停止問題は計算できないから。

チューリングの論文を読んだゲーデルは大喜びし、1951 年に開催されたアメリカ数学会での招待講演で「自分の業績を最も高い完成度で昇華させたのがチューリングだ」と絶賛しました。停止問題で不完全性定理を補強した上に、決定問題まで否定的に解決したわけだから、そりゃそうだよね。

万能チューリング・マシン

さて、どうやって「コンピュータは生まれたのか」という本題に戻りましょう。コンピュータの基礎理論は、すべて「チューリング・マシン」が土台になっていることは、最初に説明したとおりです。そして、チューリングの真骨頂はここからです。

チューリングは、あらゆるチューリング・マシンを完璧に模倣(エミュレート)できるチューリング・マシンという概念を考え出しました。これを「万能チューリング・マシン」と呼びます。

万能チューリング・マシンは、9-4を計算したければ「9-4を計算するチューリング・マシン」を呼び出してその動作を模倣し、「5」という結果を返します。323 を素因数分解したければ、「323 を素因数分解するチューリング・マシン」を呼び出してその動作を模倣し、「17」と「19」という結果を返します。

同じように、ウェブサイトを見たければ「サーバからサイト情報を取得してディスプレイに表示する」という計算を実行するチューリング・マシンを模倣しますし、写真を撮りたければ「カメラを介して得られた画像データをメモリに記録する」という計算を実行するチューリング・マシンを模倣します。

さて、賢明なる読者諸氏はお気づきと思いますが、特定の計算を実行する特殊なチューリング・マシンは「アルゴリズム」であり、それをプログラミングしたものが「ソフトウェア」です。そして、そのソフトウェアを呼び出して、その計算を模倣する(=ソフトウェアを実行する)のが万能チューリング・マシンであり、それこそが「計算機(コンピュータ)」なのです。

ほら、アナタがいま手に持っているスマホが動作する原理は「万能チューリング・マシン」にあります。また、この長いエントリーを閲覧できるようにしているソフトウェア(ブラウザ)の原理は「特殊なチューリング・マシン」にあります。あら、びっくり。

ここまで読んで、チューリングがどれほど偉大な天才であり、「コンピュータの父」と呼ばれる理由がご理解いただけたでしょうか。チューリングは、まだコンピュータが一切存在しなかった時代に、頭の中に「コンピュータ」を作り上げたわけです。しかも弱冠 24 歳で!すんごいね!

……ちなみに、このエントリーに出てきた人々は、いずれも超のつく大天才でわりとイケメンなのですが、どの人もあんまりいい死に方してません(※2)。ああ、つくづく凡人の小市民で良かったと胸をなで下ろす瞬間です。超天才たちには申し訳ないですが、皆さんも凡人であることを一緒に喜びつつ、穏やかに死ねることを祈りましょう。

イミテーションゲームとチューリング・テスト

では、最後に冒頭に紹介した「イミテーション・ゲーム」の由来を説明します。

1950 年、第二次世界大戦が終わって5年くらいが経ったころ、チューリングは「計算機械と知性」と題した論文を哲学雑誌「マインド」で発表しました。この論文でチューリングは「機械は考えることができるか?」という哲学的な問いを立て、これを検証する方法として「イミテーション・ゲーム」を提案したのです。

このゲームをざっくり説明すると、人間と機械が対話して、人間が対話している相手を機械と見破れるかどうかを試すゲームです。見破れなければ、その機械には「知性がある」と判断できる。これがかの有名な「チューリング・テスト」です。

チューリングは、自分が考えたコンピュータは、最終的に知能を持つことができると考えていました。要するに、ようやく世界最初のコンピュータが生まれたくらいの時期から人工知能の実現を確信していたのです。すごい!天才!(ちなみに、チューリングの業績を大絶賛したゲーデルは、チューリングのこの考え方には否定的な立場を取っていたらしい)

……というわけで、計算機科学の基礎を駆け足で解説しました。こんなおもしろい話に関する本格的な講義をサボり倒してたなんて、タイムマシンがあったら 20 年前の自分に小一時間ほど説教してやりたいと思った次第です。

小難しい話があまりに長くなったので、最後におもしろ動画を置いときます。私はこれを3回見て3回とも抱腹絶倒しました。おわり!

脚注

※1:停止問題の結果を応用すると、例えば「『あるプログラムがコンピュータウィルスかどうか?』を判定するアルゴリズムは存在しない」ことが分かります。もしあれば、この世からコンピュータウィルスは完全になくなるのですが、残念ながら理論的にあり得ないのです。

「なんで?アンチウィルスソフトあるじゃん」と思った方は、いろいろ誤解してます。アンチウィルスソフトは、過去のウィルスのパターンにマッチするものを「ウィルスの可能性がある」として検知しているだけですので、基本的に未知のウィルスには対応できません。なので、定期的にアップデートして新しいパターンをダウンロードする必要があるわけです。

※2:例えば、ゲーデルは、プリンストン高等研究所でアインシュタインと親交を結び、彼をして「散歩しながらゲーデルと議論する時間が楽しくて仕方ない」とまで言わしめたほどの天才ですが、アインシュタインが亡くなった後、精神に異常をきたし、絶食による飢餓状態となったそうです。すぐに病院に搬送されたらしいですが、プリンストン病院で死んでしまいました。このとき、ゲーデルの体重は、約 30 キロしかなかったと言われています。

また、チューリングは同性愛者でした。当時、イギリスでは同性愛は犯罪です。エニグマ暗号の解読でイギリスを救った英雄が、同性愛者の嫌疑をかけられて逮捕され、ホルモン注射による治療を受け入れるか投獄されるかの二択を迫られ、チューリングは研究継続のために前者を選びました。そして、1954年、わずか 42 歳で自宅で自殺してしまいました。もし、チューリングがもう少し長生きして計算機科学の発展に寄与していれば、計算機科学の歴史は大きく変わったかと考えると、とても残念な話ですね。

この記事が気に入ったら、サポートをしてみませんか?気軽にクリエイターを支援できます。

5

藤田 肇

コンピュータと人工知能の不思議な物語

計算機科学の基礎から最新の人工知能の応用まで、コンピュータに関する解説を載せています。
コメントを投稿するには、 ログイン または 会員登録 をする必要があります。