停机问题的不可判定性

反证:假设存在这样的判定器 $H$:若 $\varphi_e(x)\!\downarrow$(停机)则 $H(e,x)=1$,若 $\varphi_e(x)\!\uparrow$(永远运行)则 $H(e,x)=0$,且 $H$ 本身总是停机并给出正确答案。

利用 $H$,构造一个新程序 $D$,对输入 $e$:计算 $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$