图灵1936年的论文《论可计算数及其在判定问题上的应用》（On Computable Numbers, with an Application to the Entscheidungsproblem）奠定了现代计算机理论基础。

此论文的动机是想解决德国数学家大卫·希尔伯特（1862—1943）构想的一个问题：希尔伯特想寻找一种通用的方法来判定数理逻辑中的任意命题是否可证，寻找这种“通用的方法”被称为“判定问题”（Entscheidungsproblem）。

为此，图灵在文中首先提出现在称之为“图灵机”的计算模型，然后在第8章中给出证明“判定问题”的基本结构；在第11章中直接运用第8章的结果，得出：不存在一种通用的方法来判定数理逻辑中的任意命题是否可证，给予“判定问题”以否定性的回答，即“判定问题是不可判定的”。

我们将第8章的文本翻译如下：

一，图灵文章《论可计算数及其在判定问题上的应用》的第8章译文

第8章 对角线法的应用

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

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

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

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

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

机器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)段。

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

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

我们将首先指出，如果有一个机器E，那么就有一个一般的过程来判定给定机器M是否无限打印0。让M1是与M打印相同序列的机器，除了在由M打印的第一个0表示的位置上，M1打印0‘. M2将前两个符号0替换为􏰓0‘，依此类推。 因此，如果M要打印：

ABA01AAB0010AB...,

M2将打印：

ABA0‘1AAB0010AB...,

M1将打印：

ABA0‘1AAB0‘010AB...,

现在让F是一台机器，当它提供M的S.D时，将相继写下M，M1，M2，…（有这样的机器）的S.D，我们把F和E结合起来得到一个新的机器G，在G的第一个运动中用来写M的S.D，然后是E，验证它，:0：如果发现M从不打印0，则写M1的S.D，并且测试：0：当且仅当M1永远不打印0时打印，等等。现在让我们用E验证G。如果发现G从不打印0，那么M总是无限打印0；如果G有时打印0，那么M不无限打印0。

类似地，有一个通用的过程来判定M是否无限地打印1。通过这些过程的组合，我们有一个过程来确定M是否打印无限的数字，即我们有一个过程来判定M是否是circle-free。因此，没有机器E。

“存在一个一般过程来判定，。。。”这样的表达已经在整个章节中被使用，相当于“存在一台机器来判定……”。这样的表达只有我们在能论证我们的“可计算性”定义是合理的前提下才具有合理性。对于这些“一般过程”涉及的每一个问题都可以表示为这样一个问题：一般过程判定一个给定的整数n是否有性质G(n)［比如，G（n）可能表示‘n是可满足的’’或‘n是一个可证明公式Godel的表达］，这相当于计算一个数，如果G（n）为真，其第n个数字是1；如果G（n）为假，其第n个数字是0。

二，图灵文章《论可计算数及其在判定问题上的应用》的第8章的原文

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 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.’’

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.

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).

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.

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.

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.

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.

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).

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

ABA01AAB0010AB...,

then M1 would print

A B A 􏰓0' 1 A A B 0 0 1 0 A B . . .

and M2 would print

􏰓􏰓

A B A 0' 1 A A B 0' 0 1 0 A B . . . :

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

Similarly there is a general process for determining whether M prints 1 infinitely often. By a combination of these processes we have a process for determining whether M prints an infinity of figures, i.e. we have a process for determining whether M is circle-free. There can therefore be no machine 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 Go ̈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.

参考文献：

【1】Alan Turing, On Computable Numbers, with an Application to the Entscheidungsproblem” （https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf）

【2】Glossary of terms used by Turing （https://en.wikipedia.org/wiki/Turing%27s_proof）

1 computable number — a number whose decimal is computable by a machine, i.e. by finite means (e.g. an algorithm)

2 M — a machine with a finite instruction table and a scanning/printing head. M moves an infinite tape divided into squares each “capable of bearing a symbol”. The machine-instructions are only the following: move one square left, move one square right, on the scanned square print symbol p, erase the scanned square, if the symbol is p then do instruction aaa, if the scanned symbol is not p then do instruction aaa, if the scanned symbol is none then do instruction aaa, if the scanned symbol is any do instruction aaa [where “aaa” is an instruction-identifier].

3 computing machine — an M that prints two kinds of symbols, symbols of the first type are called “figures” and are only binary symbols 1 and 0; symbols of the second type are any other symbols.

4 figures — symbols 1 and 0, a.k.a. “symbols of the first kind”

5 m-configuration — the instruction-identifier, either a symbol in the instruction table, or a string of symbols representing the instruction- number on the tape of the universal machine (e.g. "DAAAAA = #5")

6 symbols of the second kind — any symbols other than 1 and 0

7 circular — an unsuccessful computating machine. It fails to print, ad infinitum, the figures 0 or 1 that represent in binary the number it computes

8 circle-free — a successful computating machine. It prints, ad infinitum, the figures 0 or 1 that represent in binary the number it computes

9 sequence — as in “sequence computed by the machine”: symbols of the first kind a.k.a. figures a.k.a. symbols 0 and 1.

10 computable sequence — can be computed by a circle-free machine

11 S.D – Standard Description: a sequence of symbols A, C, D, L, R, N, “;” on a Turing machine tape

12 D.N — Description Number: an S.D converted to a number: 1=A, 2=C, 3 =D, 4=L, 5=R, 6=N, 7=;

13 M(n) — a machine whose D.N is number “n”

14 satisfactory — a S.D or D.N that represents a circle-free machine

15 U — a machine equipped with a “universal” table of instructions. If U is “supplied with a tape on the beginning of which is written the S.D of some computing machine M, U will compute the same sequence as M.”

16 β’—“beta-primed”: A so-called “diagonal number” made up of the n-th figure (i.e. 0 or 1) of the n-th computable sequence [also: the computable number of H, see below]

17 u — an unsatisfactory, i.e. circular, S.D

18 s — satisfactory, i.e. circle-free S.D

19 D — a machine contained in H (see below). When supplied with the S.D of any computing machine M, D will test M's S.D and if circular mark it with “u” and if circle-free mark it with “s”

20 H — a computing machine. H computes B’, maintains R and N. H contains D and U and an unspecified machine (or process) that maintains N and R and provides D with the equivalent S.D of N. E also computes the figures of B’ and assembles the figures of B’.

21 R — a record, or tally, of the quantity of successful (circle-free) S.D tested by D

22 N — a number, starting with 1, to be converted into an S.D by machine E. E maintains N.

23 K — a number. The D.N of H.