1928 年，德国人大卫·希尔伯特提出了一个挑战，他称之为 Entscheidungsproblem，即“判定问题”：找到一种机械程序，对任何用逻辑语言写出的数学命题，都能在有限时间内回答它是真是假。如果这样的程序存在，数学就会变成一条流水线：只要写下问题，摇动手柄即可。

希尔伯特相信答案是肯定的。八年后，图灵和美国人阿隆佐·丘奇各自用不同的方法证明，答案是否定的。

一个更简单的问题

图灵没有正面进攻希尔伯特的问题。他先找到一个更朴素、却没有任何机器能回答的问题。今天人们这样讲述它：

给定一个程序和一个输入，这个程序终究会停机，还是会永远运行下去？

有时候很容易知道。把一个数加 1 的程序立刻就停。一个毫无出口地数 $1,2,3,\ldots$ 的程序永远不停。但有些很短的程序，谁也不知道答案。例如下面这个程序，它检验著名的哥德巴赫猜想——每个大于 2 的偶数都是两个素数之和：

  1. 从 $n=4$ 开始。
  2. 如果 $n$ 不是两个素数之和，就停机。
  3. 否则，把 $n$ 加 2，回到第 2 步。

这个程序停机当且仅当猜想不成立。知道它会不会停，就等于解决一个自 1742 年以来悬而未决的问题。一种判定程序是否停机的通用方法，可以一举解决这个问题以及许多其他问题。

证明

用反证法，假设存在一台机器 $P$ 能完成这项工作。它接收一个程序 $M$ 的描述和一个输入 $x$，并且总能在有限时间内回答：

$$P(M,x)=\begin{cases}\text{“停机”}&\text{若 }M\text{ 在输入 }x\text{ 上停机},\\ \text{“不停机”}&\text{若 }M\text{ 永远运行}.\end{cases}$$

有了 $P$，再造一台新机器——唱反调的 $D$。它接收一个程序 $M$ 的描述，然后这样做：

  • 问 $P$：当 $M$ 收到它自己的描述作为输入时会怎样；
  • 如果 $P$ 说“停机”，$D$ 就进入无限循环；
  • 如果 $P$ 说“不停机”，$D$ 就停机。

致命的问题来了：当 $D$ 收到它自己的描述时，会怎样？

  • 如果 $D(D)$ 停机，那么 $P$ 对 $D(D)$ 的回答是“不停机”，$P$ 错了。
  • 如果 $D(D)$ 不停机，那么 $P$ 的回答是“停机”，$P$ 又错了。

两种情况下 $P$ 都出错。所以机器 $P$ 不存在。$\blacksquare$

对角线

这个证明是康托尔对角线的近亲。想象一张无限的表：第 $i$ 行是程序 $M_i$，第 $j$ 列是输入“$M_j$ 的描述”，每格写着程序是否停机。机器 $D$ 只看对角线上的格子 $(i,i)$，并且每格都反着做。所以它不可能是任何一行：它至少在 $(i,i)$ 这一格与第 $i$ 行不同。

在 1936 年的论文中，图灵并没有恰好用“停机”这个词：他问的是一台机器会打印出无穷多位数字，还是会中途卡住。“停机问题”这个名字是后来在二十世纪五十年代才有的。想法是一样的。图灵由此得出了对希尔伯特的回答：如果有一种方法能判定任何逻辑命题，它也就能判定“机器 $M$ 会停机”这个命题，而这是不可能的。

练习：这个程序会停吗？

程序：从 $n=7$ 开始。当 $n\neq1$ 时：如果 $n$ 是偶数，$n\leftarrow n/2$；否则 $n\leftarrow3n+1$。

依次是：$7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1$。它在 16 步后停机。没有人知道它对每个初始的 $n$ 是否都会停：这就是考拉兹猜想，自 1937 年以来悬而未决。计算机已经对极大的数验证过它，但验证个例不等于证明。

练习：证明在哪里用到了机器 P？

解释为什么这个证明并没有说“任何程序都无法分析”。

证明只表明，不存在一种对所有程序都正确的方法。对许多具体的程序，判断它们是否停机很容易，而且每天都有工具在做这件事。不存在的是那台从不出错、从不拒绝回答的通用机器 $P$。

来源： Alan Turing, “On computable numbers, with an application to the Entscheidungsproblem”（1936）· Alonzo Church, “An unsolvable problem of elementary number theory”, American Journal of Mathematics（1936）· Martin Davis, The Universal Computer（2000）。

艾伦·图灵的全部主题 · ← 图灵机：用铅笔、纸带和规则来计算 · 可计算数：几乎每个数都无法计算 →

图片来源.