今天这段依然出自艾伦·图灵（Alan Turing）1936年发表的经典论文《论可计算数及其在判定问题上的应用》（Alan Turing, On Computable Numbers, with an Application to the Entscheidungsproblem, 1936），具体是文章的第八章。

原文

8. Application of the diagonal process.

It may be thought that arguments which prove that the real numbers are not enumerable would also prove that the computable numbers and sequences cannot be enumerable. It might, for instance, be thought that the limit of a sequence of computable numbers must be computable. This is clearly only true if the sequence of computable numbers is defined by some rule.

Or we might apply the diagonal process. "If the computable sequences are enumerable, let $\alpha_n$ be the $n$-th computable sequence, and let $\phi_n(m)$ be the $m$-th figure in $\alpha_n$. Let $\beta$ be the sequence with $1 - \phi_n(n)$ as its $n$-th figure. Since $\beta$ is computable, there exists a number $K$ such that $1 - \phi_n(n) = \phi_K(n)$ all $n$. Putting $n = K$, we have $1 - \phi_K(K) = \phi_K(K)$, i.e. $1$ is even. This is impossible. The computable sequences are therefore not enumerable".

The fallacy in this argument lies in the assumption that $\beta$ is computable. It would be true if we could enumerate the computable sequences by finite means, but the problem of enumerating computable sequences is equivalent to the problem of finding out whether a given number is the D.N of a circle-free machine, and we have no general process for doing this in a finite number of steps. In fact, by applying the diagonal process argument correctly, we can show that there cannot be any such general process.

The simplest and most direct proof of this is by showing that, if this general process exists, then there is a machine which computes $\beta$. This proof, although perfectly sound, has the disadvantage that it may leave the reader with a feeling that "there must be something wrong". The proof which I shall give has not this disadvantage, and gives a certain insight into the significance of the idea "circle-free". It depends not on constructing $\beta$, but on constructing $\beta'$, whose $n$-th figure is $\phi_n(n)$.

Let us suppose that there is such a process; that is to say, that we can invent a machine $\mathcal{D}$ which, when supplied with the S.D of any computing machine $\mathcal{M}$ will test this S.D and if $\mathcal{M}$ is circular will mark the S.D with the symbol "$u$" and if it is circle-free will mark it with "$s$". By combining the machines $\mathcal{D}$ and $\mathcal{U}$ we could construct a machine $\mathcal{H}$ to compute the sequence $\beta'$. The machine $\mathcal{D}$ may require a tape. We may suppose that it uses the $E$-squares beyond all symbols on $F$-squares, and that when it has reached its verdict all the rough work done by $\mathcal{D}$ is erased.

The machine $\mathcal{H}$ has its motion divided into sections. In the first $N-1$ sections, among other things, the integers $1, 2, \ldots, N-1$ have been written down and tested by the machine $\mathcal{D}$. A certain number, say $R(N-1)$, of them have been found to be the D.N's of circle-free machines. In the $N$-th section the machine $\mathcal{D}$ tests the number $N$. If $N$ is satisfactory, i.e., if it is the D.N of a circle-free machine, then $R(N) = 1 + R(N-1)$ and the first $R(N)$ figures of the sequence of which a D.N is $N$ are calculated. The $R(N)$-th figure of this sequence is written down as one of the figures of the sequence $\beta'$ computed by $\mathcal{H}$. If $N$ is not satisfactory, then $R(N) = R(N-1)$ and the machine goes on to the $(N+1)$-th section of its motion.

From the construction of $\mathcal{H}$ we can see that $\mathcal{H}$ is circle-free. Each section of the motion of $\mathcal{H}$ comes to an end after a finite number of steps. For, by our assumption about $\mathcal{D}$, the decision as to whether $N$ is satisfactory is reached in a finite number of steps. If $N$ is not satisfactory, then the $N$-th section is finished. If $N$ is satisfactory, this means that the machine $\mathcal{M}(N)$ whose D.N is $N$ is circle-free, and therefore its $R(N)$-th figure can be calculated in a finite number of steps. When this figure has been calculated and written down as the $R(N)$-th figure of $\beta'$, the $N$-th section is finished. Hence $\mathcal{H}$ is circle-free.

Now let $K$ be the D.N of $\mathcal{H}$. What does $\mathcal{H}$ do in the $K$-th section of its motion? It must test whether $K$ is satisfactory, giving a verdict "$s$" or "$u$". Since $K$ is the D.N of $\mathcal{H}$ and since $\mathcal{H}$ is circle-free, the verdict cannot be "$u$". On the other hand the verdict cannot be "$s$". For if it were, then in the $K$-th section of its motion $\mathcal{H}$ would be bound to compute the first $R(K-1)+1 = R(K)$ figures of the sequence computed by the machine with $K$ as its D.N and to write down the $R(K)$-th as a figure of the sequence computed by $\mathcal{H}$. The computation of the first $R(K)-1$ figures would be carried out all right, but the instructions for calculating the $R(K)$-th would amount to "calculate the first $R(K)$ figures computed by $H$ and write down the $R(K)$-th". This $R(K)$-th figure would never be found. I.e., $\mathcal{H}$ is circular, contrary both to what we have found in the last paragraph and to the verdict "$s$". Thus both verdicts are impossible and we conclude that there can be no machine $\mathcal{D}$.

We can show further that there can be no machine $\mathcal{E}$ which, when supplied with the S.D of an arbitrary machine $\mathcal{M}$, will determine whether $\mathcal{M}$ ever prints a given symbol (0 say).

We will first show that, if there is a machine $\mathcal{E}$, then there is a general process for determining whether a given machine $\mathcal{M}$ prints 0 infinitely often. Let $\mathcal{M}_1$ be a machine which prints the same sequence as $\mathcal{M}$, except that in the position where the first 0 printed by $\mathcal{M}$ stands, $\mathcal{M}_1$ prints $\bar{0}$. $\mathcal{M}_2$ is to have the first two symbols 0 replaced by $\bar{0}$, and so on. Thus, if $\mathcal{M}$ were to print

$$A B A 0 1 A A B 0 0 1 0 A B \ldots$$

then $\mathcal{M}_1$ would print

$$A B A \bar{0} 1 A A B 0 0 1 0 A B \ldots$$

and $\mathcal{M}_2$ would print

$$A B A \bar{0} 1 A A B \bar{0} 0 1 0 A B \ldots$$

Now let $\mathcal{F}$ be a machine which, when supplied with the S.D of $\mathcal{M}$, will write down successively the S.D of $\mathcal{M}$, of $\mathcal{M}_1$, of $\mathcal{M}_2$, ... (there is such a machine). We combine $\mathcal{F}$ with $\mathcal{E}$ and obtain a new machine, $\mathcal{G}$. In the motion of $\mathcal{G}$ first $\mathcal{F}$ is used to write down the S.D of $\mathcal{M}$, and then $\mathcal{E}$ tests it, $:0:$ is written if it is found that $\mathcal{M}$ never prints 0; then $\mathcal{F}$ writes the S.D of $\mathcal{M}_1$, and this is tested, $:0:$ being printed if and only if $\mathcal{M}_1$ never prints 0, and so on. Now let us test $\mathcal{G}$ with $\mathcal{E}$. If it is found that $\mathcal{G}$ never prints 0, then $\mathcal{M}$ prints 0 infinitely often; if $\mathcal{G}$ prints 0 sometimes, then $\mathcal{M}$ does not print 0 infinitely often.

Similarly there is a general process for determining whether $\mathcal{M}$ prints 1 infinitely often. By a combination of these processes we have a process for determining whether $\mathcal{M}$ prints an infinity of figures, i.e. we have a process for determining whether $\mathcal{M}$ is circle-free. There can therefore be no machine $\mathcal{E}$.

The expression "there is a general process for determining ..." has been used throughout this section as equivalent to "there is a machine which will determine ...". This usage can be justified if and only if we can justify our definition of "computable". For each of these "general process" problems can be expressed as a problem concerning a general process for determining whether a given integer $n$ has a property $G(n)$ [e.g. $G(n)$ might mean "$n$ is satisfactory" or "$n$ is the Gödel representation of a provable formula"], and this is equivalent to computing a number whose $n$-th figure is 1 if $G(n)$ is true and 0 if it is false.

翻译

8. 对角线法的应用

人们可能会认为，既然实数是不可枚举的，那么同样的论证也可以证明可计算数和可计算序列也是不可枚举的。例如，有人可能会以为，由可计算数构成的序列，其极限也必然是可计算的。但这显然只有当该可计算数序列是由某种明确规则定义时，这个结论才成立。

或者，我们可以尝试直接应用对角线法来进行反驳：“假设可计算序列是可枚举的，让我们把第 $n$ 个可计算序列记为 $\alpha_n$，并把 $\alpha_n$ 中的第 $m$ 个数字记为 $\phi_n(m)$。现在，定义一个新的序列 $\beta$，其第 $n$ 个数字为 $1 - \phi_n(n)$。由于 $\beta$ 是通过明确规则构造的，它理应是可计算的。因此，必然存在某个整数 $K$，使得序列 $\beta$ 就是列表中的第 $K$ 个序列，即对于所有的 $n$，都有 $1 - \phi_n(n) = \phi_K(n)$。当我们取 $n = K$ 时，就得到了 $1 - \phi_K(K) = \phi_K(K)$，这意味 $1$ 必须是偶数（或者 $2 \times \phi_K(K) = 1$），这显然是不可能的。据此，我们似乎可以得出结论：可计算序列是不可枚举的。”

上述论证的谬误，在于预设了 $\beta$ 是可计算的。如果我们能够通过有限的手段（finite means），将所有可计算序列，都有效地枚举出，$\beta$ 才是可计算的。然而，枚举所有可计算序列的问题，本质上等价于判定一个给定的数字是否是一台“无循环机器”（circle-free machine）的描述数（D.N）。而我们并没有一个通用的过程（general process）能够在有限步内完成这一判定。如果正确地应用对角线法，恰恰可以证明，这样的通用过程是不存在的。

要证明这一点，最简单直接的方法是反证法：如果存在这样的通用判定过程，那么就必然存在一台机器能够计算出上述的悖论序列 $\beta$。这个证明在逻辑上是完美的，但它可能会让读者感到困惑，觉得“一定有什么地方不对劲”。因此，本文将给出另一种证明，它不仅避免了这种困惑，还能让我们对“无循环”这一概念有更深刻的理解。这个证明不再依赖于构造序列 $\beta$，而是构造一个新的序列 $\beta'$，其第 $n$ 个数字定义为 $\phi_n(n)$。

让我们假设存在这样一个通用的判定过程。也就是说，我们可以发明一台机器 $\mathcal{D}$，当我们将任意一台计算机器 $\mathcal{M}$ 的标准描述（S.D）输入给它时，它能够对该 S.D 进行测试：如果 $\mathcal{M}$ 是“循环的”（即会死循环或停止输出），$\mathcal{D}$ 就会在 S.D 上标记符号“$u$”（unsatisfactory，不满意）；如果 $\mathcal{M}$ 是“无循环的”（即能持续输出），$\mathcal{D}$ 则标记“$s$”（satisfactory，满意）。通过将这台机器 $\mathcal{D}$ 与通用机器 $\mathcal{U}$ 相结合，我们可以构造出一台新的机器 $\mathcal{H}$ 来计算序列 $\beta'$。我们可以假设机器 $\mathcal{D}$ 使用 $F$-方格上所有符号之外的 $E$-方格作为工作区，并且当它得出结论后，会擦除所有的草稿数据。

机器 $\mathcal{H}$ 的运行过程被划分为若干个阶段。在第 $N-1$ 阶段结束时，整数 $1, 2, \ldots, N-1$ 已经被机器 $\mathcal{D}$ 逐一测试过了。其中有一部分（假设有 $R(N-1)$ 个）被判定为无循环机器的描述数（D.N）。进入第 $N$ 阶段，机器 $\mathcal{D}$ 开始测试整数 $N$。 * 如果 $N$ 是“满意的”（即它是某台无循环机器的 D.N），那么计数器加一，$R(N) = 1 + R(N-1)$。接着，$\mathcal{H}$ 会计算出 D.N 为 $N$ 的那个序列的前 $R(N)$ 位数字。并将这第 $R(N)$ 位数字记录下来，作为序列 $\beta'$ 的一个数字。 * 如果 $N$ 是“不满意的”，那么计数器保持不变，$R(N) = R(N-1)$，机器直接进入第 $N+1$ 阶段。

从 $\mathcal{H}$ 的构造过程中，我们可以看出 $\mathcal{H}$ 本身必须是无循环的。因为根据我们对 $\mathcal{D}$ 的假设，判定 $N$ 是否满意总能在有限步内完成。 * 如果 $N$ 不满意，第 $N$ 阶段会直接结束。 * 如果 $N$ 满意，意味着机器 $\mathcal{M}(N)$ 是无循环的，因此它的第 $R(N)$ 位数字一定能在有限步内被计算出来。 一旦这个数字被算出并写下，第 $N$ 阶段也就结束了。既然每个阶段都能在有限步内完成，$\mathcal{H}$ 就会持续不断地运行下去，因此 $\mathcal{H}$ 是无循环的。

现在，让我们设 $K$ 为机器 $\mathcal{H}$ 自己的描述数（D.N）。那么，当 $\mathcal{H}$ 运行到第 $K$ 阶段时，会发生什么呢？ 它必须测试 $K$ 是否满意，并给出判决“$s$”或“$u$”。 * 因为 $K$ 是 $\mathcal{H}$ 的 D.N，而我们刚才已经证明了 $\mathcal{H}$ 是无循环的，所以判决绝不可能是“$u$”。 * 另一方面，判决也不能是“$s$”。因为如果是“$s$”，那么在第 $K$ 阶段，$\mathcal{H}$ 将不得不计算以 $K$ 为 D.N 的机器（也就是它自己）所生成的序列的前 $R(K-1)+1 = R(K)$ 位数字，并将第 $R(K)$ 位写下来。前 $R(K)-1$ 位数字的计算没有问题，但要计算第 $R(K)$ 位，指令实际上变成了：“计算由 $\mathcal{H}$ 算出的前 $R(K)$ 位数字，并把第 $R(K)$ 位写下来”。这是一个死循环的递归，第 $R(K)$ 位数字永远无法被算出来。这意味着 $\mathcal{H}$ 变成了循环的。这与我们在上一段中得出的“$\mathcal{H}$ 是无循环的”结论相矛盾，也与判决“$s$”相矛盾。因此，无论是“$s$”还是“$u$”都是不可能的。唯一的结论是：根本就不存在这样的机器 $\mathcal{D}$。

我们可以进一步证明，不存在这样一台机器 $\mathcal{E}$，当向其提供任意机器 $\mathcal{M}$ 的标准描述（S.D）时，它能判定 $\mathcal{M}$ 是否曾打印过给定的符号（比如说 0）。

我们首先证明：如果存在机器 $\mathcal{E}$，那么就存在一个通用过程来判定给定的机器 $\mathcal{M}$ 是否会无限次地打印 0。 让我们构造机器 $\mathcal{M}_1$，它打印的序列与 $\mathcal{M}$ 完全相同，唯一的区别是：它将 $\mathcal{M}$ 打印的第 1 个 0 替换为 $\bar{0}$。 接着构造 $\mathcal{M}_2$，它将 $\mathcal{M}$ 打印的前 2 个 0 都替换为 $\bar{0}$，依此类推。 例如，如果 $\mathcal{M}$ 打印： $$A B A 0 1 A A B 0 0 1 0 A B \ldots$$ 那么 $\mathcal{M}_1$ 将打印： $$A B A \bar{0} 1 A A B 0 0 1 0 A B \ldots$$ 而 $\mathcal{M}_2$ 将打印： $$A B A \bar{0} 1 A A B \bar{0} 0 1 0 A B \ldots$$

现在，假设有一台机器 $\mathcal{F}$，当输入 $\mathcal{M}$ 的 S.D 时，它能依次写下 $\mathcal{M}, \mathcal{M}_1, \mathcal{M}_2, \ldots$ 的 S.D（这是可以实现的）。 我们将 $\mathcal{F}$ 与 $\mathcal{E}$ 结合，得到一台新机器 $\mathcal{G}$。$\mathcal{G}$ 的工作流程如下： 1. 利用 $\mathcal{F}$ 写下 $\mathcal{M}$ 的 S.D，用 $\mathcal{E}$ 测试它。如果 $\mathcal{E}$ 说“它从不打印 0”，则 $\mathcal{G}$ 打印一个标记 $:0:$。 2. 利用 $\mathcal{F}$ 写下 $\mathcal{M}_1$ 的 S.D，用 $\mathcal{E}$ 测试它。如果 $\mathcal{M}_1$ 从不打印 0，则 $\mathcal{G}$ 打印 $:0:$。 3. 依此类推。

现在，我们用 $\mathcal{E}$ 来测试这台新机器 $\mathcal{G}$： * 如果 $\mathcal{E}$ 判定 $\mathcal{G}$ 从不打印 0（即 $:0:$ 标记），这说明 $\mathcal{M}$ 以及所有的 $\mathcal{M}_n$ 都会打印 0。这意味着 $\mathcal{M}$ 会打印第 1 个 0，第 2 个 0，……即 $\mathcal{M}$ 会打印无限个 0。 * 如果 $\mathcal{E}$ 判定 $\mathcal{G}$ 有时会打印 0，那说明对于某个 $n$，$\mathcal{M}_n$ 从不打印 0。这意味着 $\mathcal{M}$ 最多只打印了 $n$ 个 0，并没有打印无限个。

同理，我们也存在一个通用过程来判定 $\mathcal{M}$ 是否无限次地打印 1。结合这两个过程，我们就拥有了一个判定 $\mathcal{M}$ 是否打印无限个数字（即是否为“无循环机器”）的通用过程。但我们前面已经证明了这是不可能的。因此，机器 $\mathcal{E}$ 不可能存在。

在本节中，我一直将“存在一个通用过程来判定……”等同于“存在一台机器能够判定……”。这种用法正当性的前提是我们能够为“可计算”这一概念提供充分的理由。因为每一个这类“通用过程”的问题，最终都可以转化为判定某个整数 $n$ 是否具有特定属性 $G(n)$ 的问题 [例如，$G(n)$ 可以是“$n$ 是满意的”或“$n$ 是某个可证明公式的哥德尔数”]。这实际上等价于去计算一个特定的数字：如果 $G(n)$ 为真，该数字的第 $n$ 位就是 1；如果为假，则为 0。

逐段解析

1. 对角线法 (Diagonal Process) 的经典悖论

“...$1 - \phi_K(K) = \phi_K(K)$，即 $1$ 是偶数。这是不可能的...”

• 康托尔的遗产：康托尔用对角线法证明了实数不可数。图灵在这里引用了这个逻辑，但指出如果直接套用在可计算数上，会得出一个看似矛盾的结论：既然可计算数是自然数的子集（可枚举），为什么对角线构造出的那个新数 $\beta$ 却不在这个集合里？
• 破局点：图灵指出了问题的核心——我们无法枚举所有“合法的”图灵机。
• 坏掉的机器：虽然我们可以枚举所有整数 $1, 2, 3...$，但我们不知道哪些整数代表“无循环机器”（死循环的机器不算数）。如果我们不能先把“坏机器”剔除出去，对角线法就无法构建。

示例1：对角线构造法的悖论模拟

为了更直观地理解这个过程，译者在这里用一个具体的例子来演示对角线构造法。假设我们可以把所有可计算的二进制序列都列出来（这里仅列出前 5 个作为示例）：

构造“破坏者”序列 $\beta$： 我们要构造一个新的序列 $\beta$，让它跟列表里的每一个序列都不一样。怎么做呢？我们只需要盯着对角线（加粗的部分）看，并对每一位进行二进制取反操作（即 $0 \to 1, 1 \to 0$，数学上可以表示为 $1 - x$）： * $\beta$ 的第 1 位，是 $\alpha_1$ 第 1 位的取反。$\alpha_1$ 是 0，$\beta$ 就取 1 ($1-0$)。 * $\beta$ 的第 2 位，是 $\alpha_2$ 第 2 位的取反。$\alpha_2$ 是 1，$\beta$ 就取 0 ($1-1$)。 * $\beta$ 的第 3 位，是 $\alpha_3$ 第 3 位的取反。$\alpha_3$ 是 0，$\beta$ 就取 1 ($1-0$)。 * $\beta$ 的第 4 位，是 $\alpha_4$ 第 4 位的取反。$\alpha_4$ 是 0，$\beta$ 就取 1 ($1-0$)。 * $\beta$ 的第 5 位，是 $\alpha_5$ 第 5 位的取反。$\alpha_5$ 是 1，$\beta$ 就取 0 ($1-1$)。 * ...以此类推。

于是我们构造出了序列 $\beta = 1, 0, 1, 1, 0, \ldots$

结论： * $\beta$ 不是 $\alpha_1$（第 1 位不同）。 * $\beta$ 不是 $\alpha_2$（第 2 位不同）。 * $\beta$ 不是 $\alpha_3$（第 3 位不同）。 * ... * $\beta$ 不是列表中的任何一个序列 $\alpha_n$（因为第 $n$ 位总是不同）。

这说明：无论你列出的清单有多长（哪怕是无穷长），只要是可枚举的（能按顺序排号），就总能构造出一个不在清单里的新序列。这就产生了矛盾：如果你声称“所有”可计算序列都在这个清单里了，那我刚刚构造出的 $\beta$ 算什么？

进一步的思考（关于“长宽”的疑问）： 读者可能会担心一种情况：如果序列编号 $n$ 无限增加，会不会出现“行数多于列数”的情况，导致对角线无法延伸？例如，会不会到了第 100 行，序列却只有 50 位长，从而没有第 100 位数字？如果是那样，我们是否需要调整策略（比如让对角线向下偏折）？ 答案是不需要。这里必须强调一个核心前提：每一个可计算序列本身都是无限长的二进制串（就像 $\pi$ 的小数展开一样无穷无尽）。这意味着，无论列表向下延伸到第 $n$ 行（无论 $n$ 有多大），该行的序列必然拥有第 $n$ 位数字。表格的“宽度”（位数）永远能够覆盖其“高度”（编号）。因此，标准的对角线 $\phi_n(n)$ 永远存在，我们无需进行任何复杂的移位操作即可完成反证。

2. 判定机 $\mathcal{D}$ (Decider) 的假设

“让我们假设... 我们可以发明一台机器 $\mathcal{D}$... 如果 $\mathcal{M}$ 是循环的，则用符号 $u$ 标记... 如果是无循环的，则用 $s$ 标记...”

• 停机问题 (Halting Problem)：这就是著名的停机问题的原型。
• 机器 $\mathcal{D}$ 是一个审判官。
• 给它任何一段代码（S.D），它能告诉你这段代码是会“死循环/不再输出” ($u$, unsatisfying)，还是会“正常运行” ($s$, satisfying)。
• 反证法：图灵假设这台神一般的机器 $\mathcal{D}$ 存在，然后试图导出矛盾。

3. 构造悖论机器 $\mathcal{H}$

“我们可以构造一台机器 $\mathcal{H}$... 计算 D.N 为 $N$ 的序列的前 $R(N)$ 个数字...”

• $\mathcal{H}$ 的行为：
• $\mathcal{H}$ 遍历所有数字 $1, 2, 3...$
• 用 $\mathcal{D}$ 检查当前数字 $N$ 是不是一个好机器。
• 如果是好机器，$\mathcal{H}$ 就模拟运行它，算出它的第 $R(N)$ 位数字，并抄下来。
• 如果是坏机器，直接跳过。
• $\mathcal{H}$ 是无循环的：因为 $\mathcal{D}$ 保证了 $\mathcal{H}$ 只去模拟那些“好机器”，而且只算有限位，所以 $\mathcal{H}$ 自己绝对不会死循环。它会一直产生数字。

4. 致命的矛盾

“现在令 $K$ 为 $\mathcal{H}$ 的 D.N... $\mathcal{H}$ 在其运动的第 $K$ 部分做什么？”

• 自我指涉 (Self-Reference)：
• $\mathcal{H}$ 也是一台机器，所以它也有一个编号，叫 $K$。
• 当 $\mathcal{H}$ 运行到第 $K$ 步时，它要检查它自己（编号 $K$）。
• 逻辑死结：
• $\mathcal{D}$ 会告诉 $\mathcal{H}$：你自己是无循环的（Verdict "$s$"）。
• 于是 $\mathcal{H}$ 试图计算“机器 $K$（也就是它自己）的第 $X$ 位数字”。
• 为了算出这一位，$\mathcal{H}$ 必须调用它自己。
• $\mathcal{H}$ 调用 $\mathcal{H}$，$\mathcal{H}$ 又调用 $\mathcal{H}$... 无限递归。
• 结果：$\mathcal{H}$ 变成了循环的（死循环）。
• 矛盾：$\mathcal{D}$ 刚刚才判定 $\mathcal{H}$ 是无循环的，结果 $\mathcal{H}$ 运行起来却是循环的。

示例2：机器 $\mathcal{H}$ 的“自指”悖论

为了彻底弄懂机器 $\mathcal{H}$ 的逻辑死结，我们假设 $\mathcal{H}$ 自己的编号是 $K=5$（即 $\mathcal{H}$ 是所有机器列表中的第 5 台）。 下表详细追踪了 $\mathcal{H}$ 如何利用判定机 $\mathcal{D}$ 来逐个测试其他机器，直到它遇到它自己：

致命的逻辑死结： 在第 5 阶段，$\mathcal{H}$ 接到的任务是：“计算 $\mathcal{M}(5)$ 的第 3 位数字”。 1. 你是谁？ $\mathcal{M}(5)$ 就是 $\mathcal{H}$ 自己。 2. 你要做什么？ $\mathcal{H}$ 要计算“$\mathcal{H}$ 的第 3 位数字”。 3. 怎么算？ 为了算出第 3 位，$\mathcal{H}$ 必须运行它自己的程序。 4. 运行结果？ 它的程序会再次走到第 5 阶段，再次接到任务“计算 $\mathcal{H}$ 的第 3 位数字”…… 5. 结局： 这是一个无限的“俄罗斯套娃”。$\mathcal{H}$ 永远在等待自己算出结果，结果就是死循环。

矛盾爆发： * 判定机 $\mathcal{D}$ 说：机器 $\mathcal{H}$ 是“无循环”的（判定结果 $s$）。 * 实际运行结果：机器 $\mathcal{H}$ 陷入了死循环。 * 结论：判定机 $\mathcal{D}$ 说谎了！或者更准确地说，判定机 $\mathcal{D}$ 根本不可能存在。

5. 符号判定机 $\mathcal{E}$ 的不存在性 (Rice定理的先声)

“不存在这样一台机器 $\mathcal{E}$... 能判定 $\mathcal{M}$ 是否曾打印过给定的符号...”

• 问题扩展：图灵不仅证明了“是否死循环”不可判定，还证明了“是否打印特定字符（如0）”也是不可判定的。
• 归约法 (Reduction)：
• 图灵构造了一个巧妙的逻辑链：如果能判定“是否打印0”，就能判定“是否打印无限个0”。
• 进而就能判定“是否打印无限个数字”（即是否无循环）。
• 但我们已经证明了“是否无循环”是不可判定的。
• 结论：所以一开始的假设（能判定是否打印0）必然是错的。
• 意义：这实际上是后来 Rice定理 的特例——关于程序行为的任何非平凡属性都是不可判定的。你无法写一个程序来检查另一个程序“是否会输出0”、“是否会崩溃”或“是否包含病毒”（完美查毒是不可能的）。

6. “通用过程”与“图灵机”的等价性

“这种用法只有在我们的‘可计算’定义得到辩护时才是正当的...”

• 丘奇-图灵论题 (Church-Turing Thesis)：图灵在这里进行了一次哲学升华。他认为，任何所谓的“通用过程”或“算法”，本质上都可以等价于一台图灵机。
• 定义的辩护：如果没有这个等价性，前面的证明只能说明“不存在图灵机能解决这个问题”，但不能说明“不存在任何算法能解决”。图灵将在第9章详细辩护这一点。

总结

这一章隐含了计算机科学语境下的哥德尔不完备定理。 1. 不可判定性：图灵证明了，不存在一种通用算法（机器 $\mathcal{D}$），能够预先判断任意程序是否会死循环（或是否会停止输出）。 2. 逻辑的边界：这不是因为我们可以造的计算机不够快，而是逻辑本身的局限。有些问题（如判定一个程序的好坏）在数学上就是无解的。 3. 对希尔伯特的回答：这直接否定了希尔伯特的“判定问题”（Entscheidungsproblem），即不存在一个通用算法能判定所有数学命题的真伪。