停止問題の決定不可能性

背理法で、そのような判定器 $H$ が存在すると仮定する:$\varphi_e(x)\!\downarrow$(停止する)なら $H(e,x)=1$、$\varphi_e(x)\!\uparrow$(永遠に走る)なら $H(e,x)=0$ であり、$H$ 自身は常に停止し正しい答えを出す。

$H$ を用いて、入力 $e$ に対し次のように動作する新しいプログラム $D$ を作る:$H(e,e)$ を計算し、$H(e,e)=1$ なら $D$ は無限ループに入り、$H(e,e)=0$ なら $D$ は直ちに停止する。$D$ は $H$ から実効的に構成される(単に $H$ に if 文とループを加えただけ)ので、あるプログラム索引 $d$ を持つ、すなわち $D=\varphi_d$。

ここで自己言及的な問いを立てる:$\varphi_d(d)$ は停止するか?

場合1:$\varphi_d(d)$ が停止するなら、$H$ の正しさにより $H(d,d)=1$。しかし $D$ の定義により $H(d,d)=1$ は $D$ を入力 $d$ で無限ループさせる——すなわち $\varphi_d(d)$ は停止しない。矛盾。

場合2:$\varphi_d(d)$ が停止しないなら、$H$ の正しさにより $H(d,d)=0$。しかし $D$ の定義により $H(d,d)=0$ は $D$ を入力 $d$ で停止させる——すなわち $\varphi_d(d)$ は停止する。矛盾。

どちらの場合も矛盾するので、$H$ が存在するという仮定は偽である。停止問題は決定不可能である。$\blacksquare$