第12章決定不能性

どんな機械にも解けない問題がある

前章で「計算可能」を厳密にしました。ここからが本題です。計算可能でない問題は、本当に存在するのか？ 答えはイエス。しかも、ごく自然な問題——「このプログラムは停止するか？」——が、すでに計算不能です。

証明の武器は、第1章の対角線論法です。カントールが「実数は数え尽くせない」を示したのとまったく同じ手口で、「停止判定機は存在しない」が出ます。この結果は単なる好奇心ではありません。プログラムの正しさの自動検証、数学の命題の自動判定——人類が望む多くの自動化が原理的に不可能だと告げ、次章のゲーデルの不完全性定理へ直結します。「計算の限界」と「証明の限界」は、実は同じ現象の二つの顔なのです。

停止性問題は計算不能。証明は対角線論法。ここから決定不能性が波及し、不完全性定理へ繋がる。

停止性問題

定義停止性問題

入力「機械の符号 $\langle M\rangle$ と入力 $x$ 」に対し、「 $M$ は $x$ 上で停止するか」を判定する問題。これを計算する全域機械（どんな入力にも $\mathrm{yes}/\mathrm{no}$ を必ず返す機械）が存在するか、が問い。

定理停止性問題は決定不能（チューリング）

停止性を判定する全域機械は存在しない。

証明

背理法。停止判定機 $H$ が存在すると仮定する：任意の $\langle M\rangle,x$ に対し $H(\langle M\rangle,x)=\begin{cases}\mathrm{yes}&M(x)\ \text{は停止}\\ \mathrm{no}&M(x)\ \text{は停止しない}\end{cases}$ を必ず（全域で）返す。この $H$ を使って、次の機械 $D$ を作る。 $D$ は入力 $\langle M\rangle$ に対し：

$D(\langle M\rangle):\quad H(\langle M\rangle,\langle M\rangle)=\mathrm{yes}\ \text{なら}\ \textbf{わざと無限ループ};\quad \mathrm{no}\ \text{なら}\ \textbf{停止}.$

$D$ は $H$ を部品にするだけなので機械として構成できる。ここで $D$ に自分自身の符号 $\langle D\rangle$ を入力する。

もし $D(\langle D\rangle)$ が停止するなら、 $D$ の定義より $H(\langle D\rangle,\langle D\rangle)=\mathrm{no}$ 、つまり $H$ は「 $D(\langle D\rangle)$ は停止しない」と判定したことになる。停止したのに、矛盾。
もし $D(\langle D\rangle)$ が停止しないなら、 $D$ の定義より $H(\langle D\rangle,\langle D\rangle)=\mathrm{yes}$ 、つまり $H$ は「停止する」と判定した。停止しないのに、矛盾。

どちらも矛盾。ゆえに仮定が誤りで、停止判定機 $H$ は存在しない。∎

$D(\langle D\rangle)$ ——自分自身に自分を食わせて、判定と逆をやる。カントールの対角線で「リストの $i$ 番目と $i$ 桁目で食い違う列」を作ったのと同型の一手です。「自己言及＋否定」で矛盾を生む、この構図は次章のゲーデル文「この文は証明できない」でそっくり再登場します。

決定可能性と枚挙可能性

「解ける／解けない」を集合の言葉で精密化します。問題を「 $\mathbb N$ の部分集合の帰属判定」とみなします。

定義帰納的集合・帰納的可算集合

$A\subseteq\mathbb N$ が帰納的（決定可能）とは、その特徴関数（ $x\in A$ なら $1$ 、否なら $0$ ）が計算可能で全域なこと。 $A$ が帰納的可算（r.e., 半決定可能）とは、 $A$ を出力する機械がある（ $x\in A$ なら停止して $\mathrm{yes}$ 、 $x\notin A$ なら停止しないかもしれない）こと。同値： $A$ はある計算可能関数の値域、または $A=\emptyset$ かある機械の枚挙する集合。

定理ポストの定理（決定可能性の特徴づけ）

$A$ が帰納的 $\iff$ $A$ と補集合 $\overline A$ がともに帰納的可算。

証明

$\Rightarrow$ ： $A$ 帰納的なら特徴関数で $A,\overline A$ とも決定でき、特に r.e.。 $\Leftarrow$ ： $A$ の枚挙機械 $E_A$ と $\overline A$ の枚挙機械 $E_{\overline A}$ を並行に動かす。任意の $x$ はちょうど一方に属すので、いつかどちらかが $x$ を出力して停止する。その結果で $x\in A$ か否かを全域的に判定できる。ゆえに $A$ は帰納的。∎

「両側から枚挙できれば決定できる」。この定理を停止性問題に当てると、境界がくっきり見えます。

系停止集合 K は r.e. だが帰納的でない

$K=\{\langle M\rangle: M(\langle M\rangle)\ \text{が停止}\}$ は帰納的可算（ $M(\langle M\rangle)$ を実際に走らせ、止まったら $\mathrm{yes}$ ）。だが帰納的でない（停止性の決定不能）。よってポストの定理より $\overline K$ は帰納的可算ですらない。

「半分だけ分かる（止まったら分かるが、止まらないと永遠に分からない）」が停止性問題の正体です。 $K$ が r.e. なのに非帰納的——これが「計算不能」の最も基本的な標本になります。

還元と、決定不能性の波及

一つの決定不能性から、他の問題の決定不能性を芋づる式に導く道具が還元です。

定義多対一還元・チューリング還元

$A\le_m B$ （多対一還元）：計算可能全域関数 $f$ で $x\in A\iff f(x)\in B$ 。 $A\le_T B$ （チューリング還元）： $B$ の帰属を答える“神託”を使えば $A$ が決定できる。 $A\le_m B$ かつ $B$ 決定可能なら $A$ も決定可能。対偶で、 $A$ が決定不能なら $B$ も決定不能。

「 $A$ を $B$ に翻訳できて、 $A$ が解けないなら、 $B$ も解けない」。停止性 $K$ を種にして、多くの問題の決定不能性が還元で示せます。その決定版が次の定理です。

定理ライスの定理

プログラムが計算する関数の性質のうち、自明でない（あるプログラムは満たし、あるプログラムは満たさない）ものは、すべて決定不能。例：「この関数は全域か」「恒等関数か」「値域が有限か」——どれもプログラムから機械的に判定できない。

ライスの定理は破壊的です。「プログラムの意味（入出力の振る舞い）に関する非自明な問いは、原理的に自動判定できない」。バグの完全な自動検出も、最適化の完全な自動判定も不可能——ソフトウェア工学の根本的限界を告げます。

チューリング次数とポストの問題

計算不能な集合にも「難しさの段階」があります。それを測るのがチューリング還元です。

定義チューリング次数

$A\equiv_T B$ （ $A\le_T B$ かつ $B\le_T A$ ）で割った同値類をチューリング次数という。決定可能な集合の次数を $\mathbf 0$ 、停止集合 $K$ の次数を $\mathbf{0'}$ （ジャンプ）と書く。 $\mathbf 0<\mathbf{0'}$ 。

定理ポストの問題（フリードバーグ–ムチニク）

$\mathbf 0$ と $\mathbf{0'}$ の中間の次数をもつ帰納的可算集合が存在する（ $\mathbf 0<\mathbf d<\mathbf{0'}$ ）。すなわち、決定不能だが停止性問題より真に易しい r.e. 問題がある。

ポストが問い、フリードバーグとムチニクが**優先度法（priority method）という技法で肯定的に解きました。計算不能性は「解ける／解けない」の二値ではなく、 $\mathbf 0$ の上に豊かな階層構造（半順序）が広がっている—— これを研究するのが計算可能性理論（再帰理論）**の中心テーマです。

つまずきポイント

注意よくある誤解

決定不能＝「難しい」ではない。 有限時間で解けないのではなく、どんなアルゴリズムでも原理的に解けない。計算量（P対NP）とは別の次元の話。
r.e. と決定可能は違う。 停止集合 $K$ は r.e.（半分は分かる）だが決定可能でない。「 $\mathrm{yes}$ なら必ず分かるが、 $\mathrm{no}$ は分からないかもしれない」。
停止性の証明は自己適用が核。 $D$ に $\langle D\rangle$ を入れる対角線化。この「自己言及＋否定」が次章のゲーデル文と同型。

この章のまとめ

停止性問題は決定不能。証明は $D(\langle D\rangle)$ という自己適用の対角線論法（カントールと同型）。
帰納的（決定可能）＝特徴関数が計算可能、帰納的可算（半決定可能）＝停止したら $\mathrm{yes}$ 。ポストの定理「帰納的 $\iff$ $A,\overline A$ ともに r.e.」。停止集合 $K$ は r.e. だが非帰納的。
還元で決定不能性が波及し、ライスの定理（プログラムの非自明な意味的性質はすべて決定不能）が出る。計算不能性はチューリング次数の階層をなし、ポストの問題（中間次数の存在）は優先度法で解決された。
「計算の限界」は次章の「証明の限界」（不完全性定理）と同根。自己言及＋否定という同じエンジンで動く。

次章はいよいよ本分野の最高峰——ゲーデルの不完全性定理を、対角線補題から証明します。

第12章 決定不能性