コンピュータに解けない問題はあるのか

走らせる前に知る方法は、永遠にない

「このプログラムは、実行したら無限ループに陥って戻ってこなくなるのではないか」——コードを書く人なら誰もが一度は願う検査ツールがあります。どんなプログラムでも実行前に読み取って、「これは必ず止まります」「これは止まりません」と教えてくれる判定器です。あれば世界中の開発現場が飛びつくはずなのに、そんなツールはどこにも売っていません。

技術がまだ追いついていないから、ではありません。どれほど天才的な設計者が、どれほど速い未来の計算機を使っても、原理的に作れないことが証明済みだからです。しかも証明されたのは1936年。地上にコンピュータがまだ一台も存在しない時代でした。

つまり「コンピュータに解けない問題はあるのか」への答えは、コンピュータの誕生前から「ある」と決まっています。本当に面白いのはその先です。その壁は、いったい誰の壁なのでしょうか。

「解けない」には二種類ある

先に言葉の整理をさせてください。「解けない」には、性質の違う二つがあります。一つは、解き方は分かっているのに計算時間が爆発してしまう「事実上の解けなさ」で、有名なP対NP問題はこちらの領域の話です。もう一つが、この読み物の主役である「原理的な解けなさ」——決定不能性です。どれだけ時間をかけても、すべてのケースに正しく答える単一のアルゴリズム（機械的な手順）がそもそも存在しない、という解けなさで、冒頭の無限ループ判定——のちに「停止性問題」と呼ばれるようになった問題——がその代表です。

注意したいのは、これが「個々の問題は永遠に分からない」という意味ではないことです。特定のプログラムが止まるかどうかは、個別に工夫すれば分かることも多い。存在しないのは、あらゆる場合を一括で片づける万能の手順のほうです。

数学の内側では、この意味で解けない問題があることに決着がついています。だから現在の論争の主戦場は、壁の「所有者」をめぐる問いに移っています。

立場1: 壁は宇宙そのものにある

第一の立場は、この壁をどんな機械も超えられない絶対の限界と見ます。1930年代、「計算できる」を定義しようとした複数の試み——チューリングの機械、チャーチの記号体系など——は、驚いたことにすべて同じ範囲を指しました。この一致から、「機械的に計算できるものはチューリングマシンで計算できるものと一致する」というチャーチ＝チューリングのテーゼが生まれます。さらに「物理的に作れる計算装置はすべてこの範囲に収まる」という拡張版まで認めれば、決定不能な問題は未来永劫、どんな機械にも解けません。量子コンピュータでさえ、計算を速くすることはあっても「解ける問題の範囲」自体は広げないと考えられています。

立場2: 壁は模型の限界にすぎないかもしれない

第二の立場は、その拡張に慎重です。チューリングマシンはもともと「紙と鉛筆で計算する人間」を写し取った模型であって、物理世界がそれより豊かでないという証明はない、と指摘します。哲学者ジャック・コープランドらは、チューリングマシンを超える計算——ハイパーコンピュテーションと呼ばれます——が物理的に可能かどうかは、まだ開かれた経験的問題だと論じてきました。ただし公平に言えば、そうした装置が実現できた例は一つもありません。多くの研究者は懐疑的ですが、「壁は模型の性質であって宇宙の性質だとは限らない」という論点そのものは、今も生きています。

立場3: 人間の心は、すでに壁の外にいる

第三の立場はもっと大胆です。哲学者ジョン・ルーカスや数理物理学者ロジャー・ペンローズは、ゲーデルの不完全性定理——矛盾のない十分に強い数学の体系には、真であるのに体系内では証明できない命題が残る——を根拠に、人間の数学者は機械に証明できない真理を「見て取れる」のだから、心は計算ではないと論じました。もしそうなら、あなたの頭の中では、どんなコンピュータにもできない何かが起きていることになります。刺激的な主張ですが、「人間は自分の推論に矛盾がないことを知り得ない」といった反論が数多く寄せられており、専門家の多数はこの論証は成立していないと見ています。それでも、反論の一つひとつが「計算とは何か、理解とは何か」を掘り下げる結果になった、実りの多い論争でした。

限界の証明から、コンピュータが生まれた

この壁が見つかった経緯には、科学史でも指折りの皮肉が刻まれています。

1930年9月8日、ケーニヒスベルク。引退を迎えた大数学者ダフィット・ヒルベルトは、記念講演を「我々は知らねばならない。我々は知るであろう」という言葉で結びました。数学に「永遠に知り得ないこと」など存在しない、という高らかな宣言です。ところがその前日、同じ街で開かれていた学会の討論の席で、まだ無名だった若きクルト・ゲーデルが、のちに不完全性定理と呼ばれる結果を初めて控えめに公表していました。ヒルベルトはそれを知らないまま、マイクの前に立っていたのです。

ヒルベルトはもう一つ宿題を残していました。「数学の命題が正しいかどうかを機械的な手順で判定できるか」という決定問題です。1936年、イギリスの数学者アラン・チューリングがこれに挑みます。答えるためには、まず「機械的な手順」とは何かを定義しなければなりません。そこで彼は、記号を読み書きするヘッドと無限に長いテープだけからなる架空の機械を考案しました。どんな計算手順もこの機械で表せる。それどころか、他のあらゆる機械の動作表を読み込んで真似できる一台の「万能機械」まで設計できる——これが、プログラムを内蔵する現代のコンピュータの理論的な原型です。そのうえでチューリングは、この機械には解けない問題があることを示し、決定問題に「不可能」の判定を下しました（実はアロンゾ・チャーチが一足先に、別の方法で同じ結論に達していました）。

順序に注目してください。コンピュータの設計図は、計算に何ができるかを示すためではなく、何ができないかを証明する道具として先に生まれたのです。

そしてこの壁は、紙の上の話では終わりませんでした。2015年、キュービット、ペレス＝ガルシア、ヴォルフの3人がネイチャー誌に発表した結果は物理学者を驚かせます。2次元の格子上に並んだ量子多体系について、スペクトルギャップ——いちばん低いエネルギー状態とその次の状態のあいだのエネルギー差——が存在するかどうかの判定は、停止性問題と正確に同じ意味で決定不能だというのです。物質がどう振る舞うかという具体的な問いの中に、1936年の壁がそのまま顔を出しました。

いま分かっていること、まだ分からないこと

決定不能な問題は、変わり者の例外ではないことが分かっています。たとえばヒルベルトが1900年に掲げた第10問題——整数係数の方程式に整数解があるかを判定する手順を求めよ——は、1970年、ユーリ・マチヤセビッチが先行するデイヴィス、パトナム、ロビンソンの仕事を完成させる形で「そんな手順は存在しない」と決着しました。プログラムの検証、数論、そして物理。壁は知の地図のあちこちに走っています。

壁の位置を体感できる、愉快な物差しもあります。「ビジービーバー」——n個の状態しか持たないチューリングマシンが、停止するまでに刻める最大のステップ数です。状態5個での答えは47,176,870ステップ。候補の機械は1990年に見つかっていましたが、確定したのは2024年7月、世界中の研究者と愛好家によるオンライン共同プロジェクトが、証明支援システムによる検証を完了してのことでした。たった5個でこれです。6個になると、値を確定できる見通しは立っていません。停止性問題の解けなさは、この物差しの上では「ほんの少し先がもう見えない」という手触りとして現れます。

分からないまま残っているのは、壁の所有者です。物理世界のどこかに、チューリングマシンを超える過程はあるのか。人間の数学的なひらめきは、結局は計算なのか。前者は物理学の、後者は心の哲学の現役の問いです。確かなのは、限界の発見が計算の科学を終わらせるどころか、出発させたということ。できないことの輪郭が引かれて初めて、できることの探究が始まったのです。