計算の限界（第3回/全3回）
チューリングマシンにできないこと、そしてそれが重要な理由 第2回では、チューリング完全性が計算能力の上限であることを確認した。「計算」のあらゆる妥当な形式化は等価であることがわかる。チューリングマシンより強力なものは構築できない。 しかし、チューリングマシンはすべてを解けるのだろうか？ 解けない。そして証明は驚くほど美しい。この証明はまた、数学で最も有名な結果の一つであるゲーデルの不完全性定理へとすぐに導く。 単純な問いがある：あるプログラムが与えられたとき、それは実行を終了するだろうか？ 第1回の形式化では、「プログラム」とは符号化 $\langle M, w \rangle$ のことだ：チューリングマシン $M$ とその入力 $w$ をテープ上のデータとして書いたもの。したがって停止の問いは：$M$ は $w$ で停止するか？ 停止判定器 $H$ を想像しよう。コードを入力すると「これは終了する（停止する）」か「これは永遠にループする」と教えてくれる。もし存在すれば、どんなプログラムにも使って無限ループをデプロイ前に検出し、重要なソフトウェアが常に応答を返すことを検証し、再帰関数が永遠に再帰しないことを保証できる。これほど便利なものはない。 停止問題は問う：そのような $H$ を構築できるか？特定の一つのプログラムに対してではなく、すべての $\langle M, w \rangle$ に対して正しく答える一般的な手続きを。 チューリングはそのような手続きが存在しえないことを証明した。 停止問題への「はい」と「いいえ」の答えが根本的に異なることに気づくと役に立つ。 「はい」の答えについては、プログラムを十分長く実行すればよい。一週間後に停止すれば、自信を持って「はい、停止する」と言える。 「いいえ」の答えは異なる。千年間プログラムを実行し続けて、まだ停止していないとしよう。「いいえ、永遠に停止しない」と言えるだろうか？言えない。あと一年で停止するかもしれない。プログラムを実行するだけでは、どの時点でも「いいえ」と言う資格は得られない。 この非対称性は不可能性を示唆している。では証明しよう。 背理法のために、停止問題を解く手続き $H$ があると仮定する。任意のプログラム $P$ と入力に対して、$H$ は $P$ が停止するかどうかを正しく教えてくれる。 ここで $H$ をサブルーチンとして使い、新しいプログラムを構築する。これを $Q$ と呼ぼう。プログラム $Q$ は別のプログラム $P$ を入力として受け取り、以下を行う： それだけだ。$Q$ は $P$ が自分自身で停止するかを問い、その逆を行う。 ステップ1が対角部分だ：$P$ に自分自身の記述を入力として与えている。これはラッセルのパラドックスや、対角線論法による3つの証明で探求したカントールの対角線論法と同じ自己言及のトリックだ。 さて、ここからが本番だ。$Q$ はプログラムだ。$Q$ を自分自身で実行するとどうなるか？ $Q$ が $Q$ で停止するのは、$Q$ が $Q$ で停止しない場合に限る。これは不可能だ。したがって $H$ は存在しえない。 停止問題は決定不能である。$\blacksquare$ 「決定不能」とは何を意味するか？問題が決定可能であるとは、常に停止し、常に正しいはい/いいえの答えを返す手続きが存在することだ。 停止問題は決定不能である：そのような手続きは存在しない。あらゆる停止判定器候補に対して、間違えるか永遠に実行し続けるプログラムが存在する。 停止問題は人工的な特殊ケースに見えるかもしれない。しかしこれは氷山の一角に過ぎない。ライスの定理は1953年にヘンリー・ゴードン・ライスによって証明され、これを一般化した：プログラムが計算するものに関するあらゆる非自明な性質は決定不能である。プログラムが特定の値を出力するかどうか知りたい？決定不能。ネットワークにアクセスするかどうか？決定不能。セキュリティ脆弱性を含むかどうか？決定不能。 これは静的解析ツールがときどき偽陽性を出す理由、コンパイラが常にデッドコードを除去できない理由、アンチウイルスソフトウェアがすべてのマルウェアを検出できない理由を説明する。完璧なプログラム解析は数学的に不可能なのだ。 停止問題は数学で最も有名な結果の一つを直ちに証明する。 20世紀初頭、ダヴィト・ヒルベルトは野心的な目標を提案した：数に関するすべての真なる命題を機械的に導出できる有限の公理系を見つけること。「$0$ は数である」や「$x + 0 = x$」のような基本公理から始め、推論規則を加えれば、原理的にはあらゆる真なる算術命題を証明できるはずだ。 ここで二つの概念を区別する必要がある： これらが同じものであることは自明ではない。真理は実際に何が成り立つかに関すること；証明可能性は出発点の仮定から何が導かれるかに関することだ。ヒルベルトの夢、ヒルベルト・プログラムと呼ばれるものは、算術についてこれらを一致させることだった：すべての真なる命題は証明可能であり、すべての証明可能な命題は真であるべきだ。1 もしそのような体系が存在すれば、定理証明機を構築できる：公理から始め、推論規則をあらゆる可能な方法で適用し、導出するたびに各定理を出力する。2 $1 + 1 = 2$。すべての素数にはより大きな素数がある。数に関するすべての真なる命題が一つずつ。 ここで重要な洞察がある：そのような機械は停止問題を解く。 プログラムが停止するかどうかは状態遷移の有限列に関する問いで、まさに算術で表現できる種類のものだ。もし公理系が完全なら、任意のプログラム $M$ と入力 $w$ に対して、「$M$ は $w$ で停止する」か「$M$ は $w$ で停止しない」のどちらかが証明可能だろう。列挙機は存在する方の証明を最終的に見つけ、答えが得られる。 しかし停止問題が決定不能であることはすでに証明した。したがってその体系は完全ではありえない。 ゲーデルの第一不完全性定理：基本的な算術を表現できるあらゆる計算可能な公理系3は不完全である。その体系で証明できない真なる命題が存在する。 ここが核心だ：真理は証明可能性を超える。 どんな公理を選んでも、ある命題は独立（その体系内で証明も反証もできない）となる。 後半（すべての証明可能な命題は真である）は健全性と呼ばれ、絶対に必要だ。不健全な体系は偽のことを証明してしまい、役に立たない。前半（すべての真なる命題は証明可能である）は完全性と呼ばれる。ゲーデルは完全性が不可能であることを示した。 なぜ定理を列挙できるのか？証明は有限のステップ列であり、各ステップは公理または前のステップから機械的に従う。すべての有限列を列挙し、各列の妥当性を検査し、妥当な証明の結論を出力する。すべての証明可能な命題は最終的に現れる。 体系はまた無矛盾でなければならない：$P$ と $\neg P$ の両方を証明することは決してない。無矛盾でない体系は何でも（矛盾を含めて）証明できるので、「完全性」は自明に達成可能だが無意味になる。 計算可能なものとそうでないものの境界をたどってきた。第2回では、チューリング完全性が上限であることを見た：チューリングマシン以上のことは計算できない。しかし今、この上限には穴があることがわかった。正しい答えで常に停止する手続きが存在しない問題がある。 内側：終了する手続きが書けるあらゆるはい/いいえ問題。この数は素数か？試し割りが教えてくれる。347 × 892 は何か？筆算で答えが出る。このリストをソートせよ？マージソートは正しい順序で終了する。これらは決定可能だ：常に正しい答えで停止する手続きがある。 外側：停止問題は始まりに過ぎない。ライスの定理は、プログラムの振る舞いに関するあらゆる興味深い問いは決定不能だと教えてくれる。このコードにバグはあるか？いつかネットワークにアクセスするか？この別のプログラムと等価か？すべてのプログラムに対してこれらに答えられる一般的なアルゴリズムは存在しない。そしてゲーデルは問題がより深いことを教えてくれる：有限の公理系からは決して証明できない、数に関する真なる命題が存在する。 この境界は技術に依存しない。より高速なコンピュータ、量子コンピュータ、次に何が来ようと：停止問題は決定不能のままであり、算術は不完全のままだ。いかなる機械的手続きも発見できない真理が存在する。これは計算の本質そのものに関する深い事実だ。 この記事はClaude（Opus 4.5）と協力して書きました。停止問題
直観
対角線論法
なぜこれが重要なのか
ゲーデルの不完全性定理
まとめ