图灵回应埃米尔·波斯特（Emil Post）对1936年论文“On Computable Numbers, with an Application to the Entscheidungsproblem”的评论（图灵回应Post批评 - 一封写给丘奇信件的草稿），是一份十分难得的历史文献！

波斯特的评论源自1947年发表在美国《符号逻辑杂志》（Journal of Symbolic Logic）的文章“Thue问题的递归不可解性（Recursive Unsolvability of a Problem of Thue）”（第1-11页），该评论是此文章的附录（第7-11页）。

“Thue问题”由Axel Thue在 20 世纪初提出，指给定有限字母表中的任意符号串A和B，判定A和B是否可以通过一系列简单的替换相互导出。Thue问题涉及重写系统，在后来在形式语言和计算研究中发挥了重要作用。波斯特采用归约，用Thue问题的重写过程编码和模拟图灵机的计算，通过将这两个问题联系起来，波斯特证明Thue问题的不可判定性。

波斯特在文章中除了评论图灵的原始图灵机，还特别评论了图灵1936年论文中证明Entscheidungsproblem是不可判定的二个定理：

-图灵在每种情况下都提到了所提供机器的标准描述（S.D）。但第一定理的证明以及依赖于第一定理的第二定理表明，所提供的实际上是一个正整数 n。图灵对第二定理的证明不同寻常，因为它虽然使用了第一定理的不可解性结果，但它并没有将第一定理的问题“归约（reduced）”为第二定理的问题 [Post (1944)]。事实上，第一个问题几乎肯定比第二个问题具有“更高程度的不可解性” [Post (1944)]，在这种情况下它不能“归约”为第二个问题。尽管表面上如此，但第二个不可解性证明与第一个一样，是基于不可解性定义的归谬法证明，在结论中使用第一个结果。

Turing in each case refers to the S.D of a machinebeing supplied. But the proof of the first theorem, and the second theorem depends on the first, shows that it is really a positive integer n that is supplied. Turing’s proof of the second theorem is unusual in that while it uses the unsolvability result of the first theorem, it does not ‘‘reduce’’ [Post (1944)] the problem of the first theorem to that of the second. In fact, the first problem is almost surely of ‘‘higher degree of unsolvability’’ [Post (1944)] than the second, in which case it could not be ‘‘reduced’’ to the second. Despite appearances, that second unsolvability proof, like the first, is a reductio ad absurdum proof based on the definition of unsolvability, at the conclusion of which, the first result is used.

***

题目：评论图灵的“论可计算数及其在判定问题中的应用”（埃米尔·波斯特，1947 年）

以下对图灵的“可计算性”论文的批评仅涉及其中第 [58–74]页 （注：页数参考此链接中的文章排版：https://www.cse.chalmers.se/~aikmitr/papers/Turing.pdf）。我们已经通过“通用计算机”的构造详细检查了这项工作，但以下部分中两个定理的证明仅以大纲形式给出，我们没有提供形式细节。因此，我们还以直观的形式保留了下面关于递归性陈述和替代过程的证明。

需要进行一处重大修正。在 con1 (C, a) 第[70] 页的说明中，添加以下行：None PD, R, Pa, R, R, R C。这是在机器开始动作时或由于运动超出最右边的上一个点时，完全格局以 q 结尾时引入空白扫描方块的表示 D，从而使 第 [71] 页的 fmp 正确无误。我们还可能注意到第 [58–74] 页中的以下小错误和印刷错误。第 [63] 页，在 f(C,B,a) 的说明中添加以下行：None L f(C,B,a)；第[67] 页和 p. [68]页，S.D 应该以分号开头，但不以分号结尾；第 [69]页，省略 (C2) 中的第一个 D；第[70]页，最后一段[在骨架表上方]，在第一个符号列表中添加“:”； 第 [71–72]页，将 g 替换为 q；第[71]页，在 mk 的指令中，mk 应为 mk1；第[71]页，在 sim2 的第二条指令中，将第一个 R 替换为 L；第[71]页，在 sh2 的第一条指令中，将 sh2 替换为 sh3。本文的读者应该记住，第 [63–66] 页的“示例”实际上是通用计算机表的一部分，它们完成的任务并不是针对纸带上所有可能的打印，而是针对某些打印，包括通用计算机操作产生的打印。特别是，纸带的前两个方格上印有 @，两个连续的空白方格的出现确保其右侧的所有方格都是空白的，并且通常，所指的符号位于“F 方格”上，并遵守 第 [63]页 的约定。

图灵在论文中没有完全给出对任意机器的定义，在很多地方，必须从他的开发中推断出来。首先，他的机器是一台“计算机器”，用于以二进制符号获得实数的连续数字，在这种情况下，它开始在空白纸带上运行。然而，在明确说明的情况下，机器可能会开始在先前标记的纸带上运行。从图灵经常提到纸带的开头，以及他的通用计算机处理向左运动的方式，我们得出结论，与我们的纸带不同，这纸带是从初始正方形向右的单向无限路径。

图灵主要在实践中让他的机器满足以下约定。从第一个方块开始，交替的方块称为 F 方块，其余的称为 E 方块。机器在扫描初始方块时永远不会向左移动，永远不会命令擦除或更改 F 方块上的符号，永远不会命令在前一个 F 方块为空白时在空白 F 方块上打印符号，并且对于计算机来说，永远不会命令在 E 方块上打印 0 或 1。这种约定在实践中非常有用。然而，下面描述的通用计算机的实际性能，加上图灵对上述两个定理中的第二个定理的证明，强烈表明图灵将这种约定作为任意机器定义的一部分。我们将区分图灵机和图灵约定机。

通过统一的表示方法，图灵表示了对应于我们的四元组 2 的指令集，这些指令集通过一个由七个字母组成的字符串来确定机器的行为，该字符串称为机器的标准描述 (S.D)。如果用数字代替字母，机器的 S.D 被认为是正整数的阿拉伯表示，该正整数称为机器的描述号 (D.N)。如果我们的批评是正确的，那么如果一台机器是图灵计算约定机器，并且打印无数个 0 和 1，则称其为circle-free。而所讨论的图灵的两个定理实际上如下：不存在有图灵约定机器在被提供任意正整数 n 时会确定 n 是否是circle-free的图灵计算约定机器的 D.N；不存在图灵约定机，当提供任意正整数 n 时，它将确定 n 是否是曾经打印给定符号（比如说 0）的图灵计算约定机的 D.N。

鉴于 [图灵 (1937)]，这些“非机器”结果无疑等同于相应问题的递归不可解性。5 但这两个问题都受到虚假图灵约定的影响。实际上，图灵计算机的 DN 的 n 集本身是递归的，因此 n 是 DN 的条件没有任何困难。但是，虽然不是约定机器的 DN 的 n 集是递归可枚举的，但该集合的补集，即约定机器的 DN 的 n 集，不是递归可枚举的。因此，在上述两个问题中，提出问题的答案为是的 n 集和答案为否的 n 集都不是递归可枚举的。

即使不考虑惯例条件，第一个问题也是如此。但第二个问题将成为最简单的无解问题，即非递归递归可枚举正整数集的判定问题 [(Post 1944)]。对于无限制图灵计算机的 D.N 集，例如打印 0，是递归可枚举的，但其补集不是。因此，图灵约定阻止了这种最简单的无解问题的早期出现。

同样阻止了图灵第二定理在Thue问题...不可解性证明中的应用。因为在试图将图灵第二定理问题归结为Thue问题时，当 n 导致一个答案为是的Thue问题时，我们仍然必须先确定 n 是否是图灵约定机的 D.N，然后才能给出 n 所提问题的答案，并且对于任意 n 都不能递归地做出该确定。但是，如果我们可以用递归约定替换图灵约定，那么就可以将其应用于Thue问题。对图灵通用计算机应用于任意机器时所完成的工作进行分析表明这是可以做到的。

通用计算机的设计使得当它应用于任意计算机的 S.D 时，它将产生与计算机相同的 0 和 1 序列，并且通过计算机产生的连续“完全格局”——纸带与机器的连续状态的表示——的介入。对于图灵约定机器，它就是这样做的。对于任意机器，我们必须将扫描纸带的初始方块时留下的运动方向解释为无运动。然后，通用计算机将再次产生给定机器生成的正确完全格局。但是，通用计算机打印的 0 和 1 的空间序列现在将与给定机器在空方块中打印的 0 和 1 的时间序列相同。现在，如果我们不采用图灵约定，而是采用以下约定：定义机器的指令永远不会命令打印 0 或 1（除非扫描的方块为空，或分别为 0、1），也永远不会命令擦除 0 或 1，那么图灵的论证又可以得到贯彻。而且，这种“(0, 1) 约定”是递归的，允许将其应用于Thus问题。请注意，如果一台机器实际上是图灵约定机器，我们可以删除任何与 (0, 1) 约定相矛盾的方向，而不会改变机器的行为，从而获得 (0, 1) 约定机器。但 (0, 1) 约定机器不必满足图灵约定。但是，通过将机器的每个完全格局 qi 替换为一对 qi、qi0，以分别对应于扫描的方块是 F 方块或 E 方块，并修改 F 方块上的打印以包括测试前一个 F 方块是否为空白，我们可以获得一个“(q, q0) 约定”，它也是递归的，并且可用于图灵论证和Thue问题，并且在某种意义上具有与图灵约定等价的属性。也就是说，每个 (q, q0) 约定机都是图灵约定机，而每个图灵约定机的方向都可以递归修改以产生一个 (q, q0) 约定机，其操作产生与给定机器相同的打印和擦除的时间序列和空间排列，除了在给定方块中重新打印相同的符号。

图灵约定的这些变化，在保留图灵发展的总体轮廓的同时，又允许应用于Thue问题，至少需要完全重做第二图灵定理证明的形式工作。另一方面，如果在图灵论证本身中做出以下改变，则几乎不需要增加任何形式工作，尽管仍然需要将 [图灵 (1937)] 的等价性证明扩展到不可解性概念。通过将上述结果应用于通用计算机的性能，当应用于任意机器的 S.D 时，我们看到图灵对他的第一定理的证明，无论其形式对应物是什么，都会产生以下定理。没有图灵约定机器在提供任意正整数 n 时，会确定 n 是否是任意图灵机的 D.N，该图灵机无限次地在空方块中打印 0 和 1。现在给定一个任意正整数 n，如果该 n 是图灵机 M 的 D.N，则将通用计算机器应用于 M 的 S.D 以获得机器 M+。由于 M+ 满足图灵约定，因此无论图灵对其第二定理的形式证明是什么，它都可以在当前证明中完整使用，并且通过其第一定理的新形式，将产生以下可用结果。没有一台机器在提供任意正整数 n 时能够确定 n 是否是打印给定符号（例如 0）的任意图灵机的 D.N。

这些替代程序假设保留了图灵的通用计算机。但是，鉴于上述讨论，作者认为图灵对可计算数的过分关注已经破坏了他对图灵机的整个开发。因此，我们建议基于 [‘Thue问题的递归不可解性’] 中给出的公式重新开发图灵机。这可以很容易地包括可计算数，方法是将0和1的可计算序列定义为任意图灵机打印0和1的时间序列，前提是这种打印次数是无限的。通过在图灵的完全格局中添加最后执行的动作的表示，对图灵的方法进行一些更改将产生一台通用计算机，它将这种时间序列转换为空间序列。在设置这台和其他特定机器时，将遵循图灵的惯例作为有用的实践。但它不会影响任意图灵机的理论。

原文：

RECURSIVE UNSOLVABILITY OF A PROBLEM OF THUE EMIL L. POST

https://www.wolframscience.com/prizes/tm23/images/Post2.pdf

Appendix : On Computable Numbers, with an Application to the Entscheidungsproblem. A Critique. (1947 ) Emil Post

The following critique of Turing’s ‘‘computability’’ paper [Chapter 1] concerns only pp. [58–74, the numbers of pages, see https://www.cse.chalmers.se/~aikmitr/papers/Turing.pdf ] thereof. We have checked the work through the construction of the ‘‘universal computing machine’’ in detail, but the proofs of the two theorems in the section following are there given in outline only, and we have not supplied the formal details. We have therefore also left in intuitive form the proofs of the statements on recursiveness, and alternative procedures, we make below.

One major correction is needed. To the instructions for con1 (C, a) p. [70], add the line: None PD, R, Pa, R, R, R C. This is needed to introduce the representation D of the blank scanned square when, as at the beginning of the action of the machine, or due to motion right beyond the rightmost previous point, the complete configuration ends with a q, and thus make the fmp of p. [71] correct. We may also note the following minor slips and misprints in pp. [58–74]. Page [63], to the instructions for f(C,B,a) add the line:None L f(C,B,a);p.[67]and p. [68], the S.D should begin, but not end, with a semicolon; p. [69], omit the first D in (C2); p. [70], last paragraph [above skeleton table], add ‘‘:’’ to the first list of symbols; pp. [71–72], replace g by q; p. [71], in the instruction for mk, mk should be mk1; p. [71], in the second instruction for sim2, replace the first R by L; p. [71], in the first instruction for sh2, replace sh2 by sh3. A reader of the paper will be helped by keeping in mind that the ‘‘examples’’ of pages [63–66] are really parts of the table for the universal computing machine, and accomplish what they are said to accomplish not for all possible printings on the tape, but for certain ones that include printings arising from the action of the universal computing machine. In particular, the tape has @ printed on its first two squares, the occurrence of two consecutive blank squares insures all squares to the right thereof being blank, and, usually, symbols referred to are on ‘‘F-squares’’, and obey the convention of p. [63].

Turing’s definition of an arbitrary machine is not completely given in his paper, and, at a number of points, has to be inferred from his development. In the first instance his machine is a ‘‘computing machine’’ for obtaining the successive digits of a real number in dyadic notation, and, in that case, starts operating on a blank tape. Where explicitly stated, however, the machine may start operating on a tape previously marked. From Turing’s frequent references to the beginning of the tape, and the way his universal computing machine treats motion left, we gather that, unlike our tape, this tape is a one-way infinite aVair going right from an initial square.

By a uniform method of representation, Turing represents the set of instructions, corresponding to our quadruplets,2 which determine the behavior of a machine by a single string on seven letters called the standard description (S.D) of the machine. With the letters replaced by numerals, the S.D of a machine is considered the arabic representation of a positive integer called the description number (D.N) of the machine. If our critique is correct, a machine is said to be circle-free if it is a Turing computing convention-machine which prints an infinite number of 0’s and 1’s.3 And the two theorems of Turing’s in question are really the following. There is no Turing convention-machine which, when supplied with an arbitrary positive integer n, will determine whether n is the D.N of a Turing computing convention-machine that is circle-free. There is no Turing convention-machine which, when supplied with an arbitrary positive integer n, will determine whether n is the D.N of a Turing computing convention-machine that ever prints a given symbol (0 say).

In view of [Turing (1937)], these ‘‘no machine’’ results are no doubt equivalent to the recursive unsolvability of the corresponding problems. But both of these problems are infected by the spurious Turing convention. Actually, the set of n’s which are D.N’s of Turing computing machines as such is recursive, and hence the condition that n be a D.N offers no difficulty. But, while the set of n’s which are not D.N’s of convention-machines is recursively enumerable, the complement of that set, that is, the set of n’s which are D.N’s of convention-machines, is not recursively enumerable. As a result, in both of the above problems, neither the set of n’s for which the question posed has the answer yes, nor the set for which the answer is no, is recursively enumerable.

This would remain true for the first problem even apart from the convention condition. But the second would then become that simplest type of unsolvable problem, the decision problem of a non-recursive recursively enumerable set of positive integers [(Post 1944)]. For the set of n’s that are D.N’s of unrestricted Turing computing machines printing 0, say, is recursively enumerable, though its complement is not. The Turing convention therefore prevents the early appearance of this simplest type of unsolvable problem.

It likewise prevents the use of Turing’s second theorem in the . . . unsolvability proof of the problem of Thue.6 For in attempting to reduce the problem of Turing’s second theorem to the problem of Thue, when an n leads to a Thue question for which the answer is yes, we would still have to determine whether n is the D.N of a Turing convention-machine before the answer to the question posed by n can be given, and that determination cannot be made recursively for arbitrary n. If, however, we could replace the Turing convention by a convention that is recursive, the application to the problem of Thue could be made. An analysis of what Turing’s universal computing machine accomplishes when applied to an arbitrary machine reveals that this can be done.

The universal computing machine was designed so that when applied to the S.D of an arbitrary computing machine it would yield the same sequence of 0’s and 1’s as the computing machine as well as, and through the intervention of, the successive ‘‘complete configurations’’—representations of the successive states of tape versus machine—yielded by the computing machine. This it does for a Turing convention-machine.7 For an arbitrary machine, we have to interpret a direction of motion left at a time when the initial square of the tape is scanned as meaning no motion.8 The universal computing machine will then yield again the correct complete configurations generated by the given machine. But the space sequence of 0’s and 1’s printed by the universal computing machine will now be identical with the time sequence of those printings of 0’s and 1’s by the given machine that are made in empty squares. If, now, instead of Turing’s convention we introduce the convention that the instructions defining the machine never order the printing of a 0 or 1 except when the scanned square is empty, or 0, 1 respectively, and never order the erasure of a 0 or 1, Turing’s arguments again can be carried through. And this ‘‘(0, 1) convention’’, being recursive, allows the application to the problem of Thue to be made.9 Note that if a machine is in fact a Turing convention-machine, we could strike out any direction thereof which contradicts the (0, 1) convention without altering the behavior of the machine, and thus obtain a (0, 1) convention-machine. But a (0, 1) convention-machine need not satisfy the Turing convention. However, by replacing each internal-configuration qi of a machine by a pair qi , qi 0 to correspond to the scanned square being an F- or an E-square respectively, and modifying printing on an F-square to include testing the preceding F-square for being blank, we can obtain a ‘‘(q, q0) convention’’ which is again recursive, and usable both for Turing’s argu- ments and the problem of Thue, and has the property of, in a sense, being equivalent to the Turing convention. That is, every (q, q0) convention- machine is a Turing convention-machine, while the directions of every Turing convention-machine can be recursively modiWed to yield a (q, q0) convention-machine whose operation yields the same time sequence and spatial arrangement of printings and erasures as does the given machine, except for reprintings of the same symbol in a given square.

These changes in the Turing convention, while preserving the general outline of Turing’s development and at the same [time] admitting of the application to the problem of Thue, would at least require a complete redoing of the formal work of the proof of the second Turing theorem. On the other hand, very little added formal work would be required if the following changes are made in the Turing argument itself, though there would still remain the need of extending the equivalence proof of [Turing (1937)] to the concept of unsolvability. By using the above result on the performance of the universal computing machine when applied to the S.D of an arbitrary machine, we see that Turing’s proof of his first theorem, whatever the formal counterpart thereof is, yields the following theorem. There is no Turing convention-machine which, when supplied with an arbitrary positive integer n, will determine whether n is the D.N of an arbitrary Turing machine that prints 0’s and 1’s in empty squares infinitely often. Now given an arbitrary positive integer n, if that n is the D.N of a Turing machine M, apply the universal computing machine to the S.D of M to obtain a machine M+. Since M+ satisWes the Turing convention, whatever Turing’s formal proof of his second theorem is, it will be usable intact in the present proof, and, via the new form of his first theorem, will yield the following usable result. There is no machine which, when supplied with an arbitrary positive integer n, will deter- mine whether n is the D.N of an arbitrary Turing machine that ever prints a given symbol (0 say).

These alternative procedures assume that Turing’s universal computing machine is retained. However, in view of the above discussion, it seems to the writer that Turing’s preoccupation with computable numbers has marred his entire development of the Turing machine. We therefore suggest a redevelopment of the Turing machine based on the formulation given in [‘Recursive Unsolvability of a Problem of Thue’11]. This could easily include computable numbers by defining a computable sequence of 0’s and 1’s as the time sequence of printings of 0’s and 1’s by an arbitrary Turing machine, provided there are an infinite number of such printings. By adding to Turing’s complete configuration a representation of the act last performed, a few changes in Turing’s method would yield a universal computing machine which would transform such a time sequence into a space sequence. Turing’s convention would be followed as a matter of useful practice in setting up this, and other, particular machines. But it would not infect the theory of arbitrary Turing machines.