哥德尔的证明得出结论，“说谎者悖论”（说自己是不可证明的命题）是Peano形式系统中“不可判定命题”。我认为，此命题不是Peano形式系统中的真实命题，所以作为逻辑证明，哥德尔的证明是无效的。而“停机问题”继续踏着哥德尔的脚步，这是我为什么解读“停机问题”的原因。

那么，什么是“不可判定命题”？形式系统中是否存在真实的“不可判定命题”？

我们来看图灵在他1936年的论文中是如何回答这些问题的。

一，图灵求解Entscheidungsproblem的框架

图灵求解Entscheidungsproblem是采取多层次递进的方式。

图灵首先在第8章证明了：不可能有机器E，当提供给任意机器M的标准描述时，E将确定M是否打印出一个给定的符号（例如0）。

然后在论文的第11章，图灵证明Entscheidungsproblem不可解。图灵说：

- 我建议指出，不存在判定函数计算K（注：K指一阶谓词）中的给定公式A是否可证明的通用过程，也就是说，不存在机器在提供这些公式中任何一个公式A时，最终会说A是否可以证明。

I propose, therefore, to show that there can be no general process for determining whether a given formula A of the functional calculus K is provable (Note: K refers to the first-order predicate), i.e. that there can be no machine which, supplied with any one A of these formulae, will eventually say whether A is provable.

Therefore, Turing gave a definition of decision problem such that « there is a general process for determining . . . ».

关于证明的思路，图灵说：

- 对应于每个计算机器M，我们构造一个公式Un(M)，并且证明，如果存在通用的方法判定Un(M)是否可证明，那么就存在通用方法判定M是否可打印0。

Corresponding to each computing machine M we construct a formula Un(M) and we show that, if there is a general method for determining whether Un(M) is provable, then there is a general method for determining whether M ever prints 0.

- Un (M)的解释是“在M的某个格局下S1（即0）出现在纸带上”，也就是说，Un (M)是用谓词公式模拟机器M的计算。与此对应，我证明：

引理1. 如果S1出现在某个格局的纸带上，那么Un (M)是可证明的。

引理2. 如果Un (M)是可以证明的，那么S1出现在某个格局的纸带上。

Un (M) has the interpretation ‘‘in some complete configuration of M, S1 (i.e. 0) appears on the tape’’. Corresponding to this I prove that

Lemma 1. If S1 appears on the tape in some complete configuration of M, then Un (M) is provable.

Lemma 2. If Un (M) is provable, then S1 appears on the tape in some complete configuration of M.

在证明了引理1和引理2后，图灵说：

- 我们现在可以指出，Entscheidungsproblem不可解。 让我们假设相反， 然后有一个通用（机械）过程用于判定 Un (M)是否可证明，根据引理1和2，这意味着有一个过程来判定M是否打印0，而根据第8章，这是不可能的。 因此，Entscheidungsproblem问题无法求解。

We are now in a position to show that the Entscheidungsproblem cannot be solved. Let us suppose the contrary. Then there is a general (mechanical) process for determining whether Un (M) is provable. By Lemmas 1 and 2, this implies that there is a process for determining whether M ever prints 0, and this is impossible, by §8. Hence the Entscheidungsproblem cannot be solved.

二，可计算数的枚举问题

在第8章 图灵对角线法进行修改用来证明可计算数和可计算序列不可枚举，于是不存在机器E判定机器M是否打印一个给定的符号，图灵说：

- 人们会想，证明实数不可枚举的论证也可用来证明可计算数和可计算序列不可枚举。比如，人们会想，可计算数的序列的极限一定是可计算的，很明显，这只有当可计算数的序列由某个规则定义时才是真实的。

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.

- 或许，我们可以运用对角线法，“如果可计算序列是可枚举的，令an是第n个可计算序列，Φn(m)是an的第m个数字；假设β是1-Φn(n) 作为第n个数字的序列。既然β是可计算的，就存在一个整数K，使得对所有的n，有1-Φn(n) = Φk(n)。特别地，令n=K，有1=2ΦK(K)，即1是偶数。但是，这是不可能的，于是可计算序列不可枚举。”

Or we might apply the diagonal process. ‘‘If the computable sequences are enumerable, let an be the n-th computable sequence, and let Φn(m) be the m-th figure in an. Let β be the sequence with 1-Φn(n) as its n-th figure. Since β is computable, there exists a number K such that 1-Φn(n) = Φk(n) all n. Putting n=K , we have 1=2ΦK(K), i.e. 1 is even. This is impossible. The computable sequences are therefore not enumerable.’’

- 此论证荒谬之处在于，“β是可计算的”假设，如果我们能通过有限手段枚举可计算序列，此假设才为真，但是枚举可计算序列，与判断给定的一个数是否为一个“circle-free”机器的D.N的问题等价，我们没有在有限步骤内这样做的通用过程。事实上，通过正确运用对角线法，我们可以指出不存在这样的通用过程。

The fallacy in this argument lies in the assumption that β 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.

- 最简单最直接的证明是指出，如果这样的通用过程存在，那么有一台机器计算β。此证明虽然很健全，但有缺点，它可能让读者有种感觉“一定有什么地方不对劲”。我将给出的证明没有这样的缺点，并对“circle-free”概念的意义给出某种洞察。它不依靠构造β，而是构造β’，其第n个数字是Φn(n)。

The simplest and most direct proof of this is by showing that, if this general process exists, then there is a machine which computes β. 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 β, but on constructing β' , whose n-th figure is Φn(n).

- 假设有这样一个过程，即我们可以发明一种机器D，任给一个计算机器M的S.D，D将验证这个S.D，如果M是“circular”，就标记u，如果M是“circle-free”，就标记s。通过组合D和U我们能构造机器H来计算β’。机器D需要一条纸带，我们可以假设除了用F-squares的所以符号外，还用E-squares的符号，当D作出判断时，它所做的粗糙的工作被删除。

Let us suppose that there is such a process; that is to say, that we can invent a machine D which, when supplied with the S.D of any computing machine M will test this S.D and if 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 D and U we could construct a machine H to compute the sequence β’. The machine 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 D is erased.

图1：图灵的证明修改康托尔的对角线法

- 机器H的运动分成若干段。在前N-1段，除了别的事，整数1，2，...，N-1被写下来，由机器D验证。比如R(N-1)个整数，已经被发现是“circle-free machine”的D.N。在第N段，机器D验证整数N。如果N是满足的，即它是“circle-free machine”的D.N，那么R(N)=1+R(N-1)，D.N是N的序列的前R(N)个数被计算。这个序列的第R(N)个数字被写下，作为由H计算的序列β’的一个数字。如果N不是满足的，那么R(N)=R(N-1)，机器继续运动到第(N+1)段。

The machine H has its motion divided into sections. In the first N-1 sections, among other things, the integers 1, 2, . . . , N-1 have been written down and tested by the machine 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 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 b’ computed by H . If N is not satisfactory, then R(N)=R(N-1) and the machine goes on to the (N+1) section of its motion.

- 从H的结构可以看出，H是“circle-free”，H的每一段运动经过有限步骤后有个结果，因为由我们关于D的假设，有限步骤内可判断N是否可满足。如果N是满意的，就意味着机器M(N)的D.N是“circle-free”，于是它的第R(N)数可以在有限步骤内计算。当这个数被计算，作为β’的第R(N)个数字写下来，第N段结束，于是H是“circle-free”。

From the construction of H we can see that H is circle-free. Each section of the motion of H comes to an end after a finite number of steps. For, by our assumption about 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 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 β', the N-th section is finished. Hence H is circle-free.

- 现在，令K是H的D.N。H在第K段的运动中做什么？它必须检验K是否是满足的，给出一个判断«s»或«u»。既然K是H的D.N，且K是“circle-free”，其判断不可能是«u»。另一方面，判断又不能是«s»，因为如果是«s»，那么在H运动第K段时，将被限制在计算由D.N是K的机器计算的序列的前R(K-1)+1=R(K)个数字，写下作为由H计算的序列的第R(K)数字。计算前R(K)-1数字将顺利进行，但是计算第R(K)个的指令将是“计算由H计算的前R(K)数字，且写下第R(K)个”。 这第R(K)个数字从未被发现，即H是“circular”，与我们在最后一段落发现的和判断«s»相反。于是二个判断都是不可能的，于是我们得出不存在机器D。

Now let K be the D.N of H. What does 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 H and since 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 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 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., 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 D.

- 我们可以进一步指出，没有机器E，当给它提供任意机器M的S.D时，判定M是否打印一个给定的符号（比如0）。

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

三，停机问题

学术界一致认为，停机问题是图灵在1936年提出的，并被认为是计算机科学和计算理论的基本成果之一。

停机问题一般表达为：是否存在一个算法判定任给的一个算法在一个输入下停机或永远运行？

停机问题证明的一般思路是：假设有这样一种算法，那么一定有图灵机H“判定”图灵机Tn在作用于数m时是否停机：如果Tn不停机，H就输出0；如果Tn停机，就输出1：

H(n;m) = 0 if Tn(m) = □; 1 if Tn(m) stops.

列出了所有可能的图灵机作用于所有可能的输入，运用图灵机H进行判断，在此基础上直接运用Cantor的对角线法，通过反证法证明不存在图灵机H，即“停机问题”不可判定。 

图2：停机问题证明直接运用康托尔的对角线法

四，停机问题 vs Entscheidungsproblem

图灵1936年的论文讨论了Entscheidungsproblem。从上面的解读来看，图灵在第8节讨论可计算数的枚举问题，旨在证明没有任何算法可以确定任何给定的算法是否可以写下一个给定的符号；而停机问题，旨在证明没有任何算法可以确定任何给定的算法在给定的输入下是否停机或永远运行。在这种情况下，Halting问题确实与可计算数的枚举问题有关。

然而，正如我们的解读(“停机问题”（4） - “可计算数”的消失)，可计算数的概念已经从停机问题中消失了，停机问题的证明要么利用说谎者悖论，要么复制康托尔的对角线过程，这正是图灵所批评的! 基于这一批评，图灵重新审视了康托尔的对角线过程（比较图1和图2），并证明了可计算数是不可判定的，也就是说，没有任何算法可以确定任何给定的算法是否能写下一个给定的符号。因此，“停机问题”并不等同于“可计算数的枚举问题”，而停机问题不可判定的结论只是图灵证明的一个自然推论。

因此，将可计算数的枚举问题或者Entscheidungsproblem简化为“停机问题”，无论从问题的内涵还是证明来看，都是非常值得怀疑的。这种未经深入讨论的简化不仅会严重歪曲图灵的工作，而且也会误导人们对不可判定问题的理解，造成解决P vs. NP问题的困境，让认识如今人工智能中人机关系失去了方向，。。。

参考文献：

Turing, A. M. (1937). "On Computable Numbers, with an Application to the Entscheidungsproblem". 

https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf