定理証明済み

停止問題の決定不能性

内容

任意のプログラム(チューリング機械) $P$ と入力 $x$ を受け取り、 $P$ を $x$ で実行したときに停止するかどうかを、常に有限時間で正しく判定できるアルゴリズムは存在しない。

なぜ正しいのか?

そのような停止判定器 $H$ が存在すると仮定する。プログラム $D$ を、入力プログラム $Q$ に対して、 $H$ を用いて $Q$ が自分自身に対して実行されたとき停止するかを調べ、その逆の動作をする(すなわち $Q$ が停止するなら無限ループし、 $Q$ がループするなら停止する)ように構成する。 $D$ を自分自身を入力として実行すると、いずれの場合も矛盾が生じるため、 $H$ は存在し得ない。

証明の概略

対角線論法:判定器 $H(P,x)$ が存在し、 $P$ が $x$ で停止するかを出力すると仮定する。 $D(P) =$ 「 $H(P,P)$ が『停止する』と答えるなら無限ループする、そうでなければ停止する」と定義する。そして $D(D)$ が停止するかを問う。もし停止するなら、定義により $H(D,D)$ は「無限ループする」と答えたはずで矛盾する。もし無限ループするなら $H(D,D)$ は「停止する」と答えたはずで、これも矛盾する。したがって $H$ は存在し得ない。

証明者

1936年に証明アラン・チューリング

この定理を使うトピック

再帰関数とチューリング機械ゲーデルの不完全性定理

参考文献

Alan M. Turing (1936). On Computable Numbers, with an Application to the Entscheidungsproblem · DOI:10.1112/plms/s2-42.1.230
Michael Sipser (2012). Introduction to the Theory of Computation