递归函数与图灵机

这正是无论何种杀毒软件、编译器或集成开发环境,都无法在完全一般的意义下完美检测出死循环、死代码或"这个函数总是崩溃"的数学原因——这不是当今工程技术的局限,而是一堵坚硬的数学壁垒。

反证:假设存在这样的判定器 $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$

这一个定理立刻排除了诸如"这个程序是否计算零函数""这个程序是否计算全函数""这两个程序是否等价"等无数关于程序行为的自然问题的算法——无需为每个问题单独构造对角线论证,一击即中。

不失一般性,假设处处未定义的函数 $\emptyset$(由一个对任何输入都永不停机的程序所计算)不具有性质 $P$——否则改用补性质 $\lnot P$ 论证,它可判定当且仅当 $P$ 可判定。由于 $P$ 非平凡,固定某个程序 $e_0$,其函数 $\varphi_{e_0}$ 具有性质 $P$。

反证:假设 $P$ 可由某算法 $D$ 判定(给定一个程序索引,$D$ 停机并正确报告该程序的函数是否具有性质 $P$)。我们把停机问题归约到 $P$,从而与定理1矛盾。

对任意一对 $(e,x)$,有效地构造(通过简单的文本操作——克莱尼的 s-m-n 定理)一个新程序 $e'$,它对任意输入 $y$:先模拟程序 $e$ 在输入 $x$ 上运行;一旦该模拟停机,$e'$ 就接着模拟程序 $e_0$ 在输入 $y$ 上运行并输出其结果。

考察两种情形。若 $e$ 在 $x$ 上停机:对 $e$ 在 $x$ 上的模拟会结束,于是 $e'$ 在所有输入上的行为都与 $e_0$ 完全一致,即 $\varphi_{e'}=\varphi_{e_0}$——它具有性质 $P$(因为 $P$ 是语义的,只依赖于所计算的函数,而 $\varphi_{e_0}$ 具有 $P$)。若 $e$ 在 $x$ 上不停机:对 $e$ 在 $x$ 上的模拟永不结束,于是 $e'$ 在任何输入 $y$ 上都永远到不了模拟 $e_0$ 的那一步;因此 $\varphi_{e'}$ 就是处处未定义的函数 $\emptyset$,按假设它不具有性质 $P$。

所以:$e$ 在 $x$ 上停机 $\iff$ $\varphi_{e'}$ 具有性质 $P$ $\iff$ $D(e')$ 回答"是"。由于 $(e,x)\mapsto e'$ 可计算,算法"由 $(e,x)$ 计算出 $e'$,再运行 $D(e')$"就能判定停机问题——与定理1矛盾。故不存在这样的 $D$:$P$ 不可判定。$\blacksquare$