1，译文

对于给定的图灵机 M，停机问题是指判定给定有限字符串 u 是否在纸带上以 u 为起始点，纸带头位于 u 的初始符号上时，M 最终会停机。

对于给定的图灵机 M 和给定符号 S0，打印问题是指判定给定有限字符串 u 是否在纸带上以 u 为起始点，纸带头位于 u 的初始符号上时，M 最终会上出现符号 S0。

当然，众所周知，对于这些问题中的每一个，都可以展示一台图灵机，对于该图灵机，它在算法上是不可解的。在本文中，Lucas 讨论了这些问题，并指出，尽管它们的不可解程度相同，但这些问题是不同的，因为可以给出一个图灵机的例子，该图灵机具有不可解的停机问题，但具有可解的打印问题，反之亦然。我认为值得注意的是，通过对其定义指令表进行非常简单的更改，可以将这两个问题中任何一个问题的不可解示例转变为相对于另一个问题不可解的示例。

因此，假设 M 是一台不可解的打印问题的图灵机。我们分两步修改其指令表，将其转换为具有无法解决的停机问题的机器。

(1) 填写表格，使每对机器状态和符号 q、S 都有一行。这些行应该是不会发生任何变化的虚拟行：它们应该只是重新打印 S，然后返回到相同的状态 q。

(2) 引入一个新的停机状态 q0，并通过将 q0 设为这些行中的最后一个符号来更改调用打印 S0 的行。

显然，修改后的机器最终会以给定的输入停机，以防原始机器最终会使用该输入打印 S0。

文献中经常提到停机问题的不可解性，通常归功于图灵。有人提醒我，“停机问题”这个词第一次出现似乎是在我 1958 年出版的书中对这个问题的论述 [《可计算性和不可解性》，麦格劳-希尔信息处理和计算机系列丛书，麦格劳-希尔公司，纽约，1958 年；MR0124208]。我当然不会因为做了比想出一个好名字更多的事而居功自傲，正如Lucas 指出的那样，数学内容在六年前出版的 [S. C. Kleene，《元数学导论》，D. Van Nostrand 公司，纽约，1952 年；MR0051790] 中非常明确。 Lucas还指出，在 [同上] 中，我写道：“这些问题本质上的不可解性是由图灵首先获得的”。

在讨论 A. M. Turing 的 [Proc. London Math. Soc. (2) 42 (1936), no. 3, 230–265; MR1577030；更正，Proc. London Math. Soc. (2) 43 (1937), no. 7, 544–546; MR1575661] 时， Lucas写道：“图灵的计算概念不关注任何停机行为”，这是事实，停机问题本身肯定不会在 [A. M. Turing，同上] 中找到，然而我认为值得在更广泛的背景下考虑这些问题。当图灵着手制定可计算性的精确特征时，他已经对数值计算，特别是实数计算有着浓厚的兴趣和经验。他对计算 zeta 函数零点的方法特别感兴趣。因此，当他寻求一种精确表达算法可计算性概念的方法时，他自然会想到可计算实数。他的机器在空纸带上启动，并打算在纸带上打印无限的 0 和 1 序列，从而定义区间 [0,1] 中的实数。这对图灵来说是一个自然的选择，但对于可计算性理论的发展来说却是一个不幸的选择。他称打印这种序列的机器为circle-free机器，并使用康托对角化来表明判定给定机器（由其指令表给出）是否circle-free的问题是不可判定的。 （杰克·科普兰建议将确定给定机器是否无环的问题称为 SATIS。我认为这是一个糟糕的选择，因为它会与 SAT 混淆，SAT 是许多研究人员研究过的 NP 完全可满足性问题。）但正如卢卡斯详细展示的那样，这个问题的度数为 0′′，因此不适合证明判定问题的不可解性——图灵的目标。为此，他非常巧妙地利用circle-free问题的不可解性来证明我所说的问题的不可解性：

图灵打印问题：给定图灵机和给定符号 S0，判定该机器是否会从空白纸带启动并打印 S0。

当然，就目前情况而言，不能像 [M. D. Davis，同上] 中所做的那样，为不可解的打印问题提供一台机器，但并非一切都失去。作为图灵打印问题的结果，很容易看出，图灵的通用机器存在不可解的打印问题：如果我们有一个算法来判定具有给定输入的通用机器最终是否会打印 S0，我们可以向其输入给定机器的指令表（严格来说是它的代码），以确定该机器是否会从空白纸带启动并打印 S0。

2. 原文

https://mathscinet.ams.org/mathscinet/article?mr=4256190

The Halting Problem for a given Turing machine M is the problem to determine of a given finite string u whether M will eventually halt when started with u on its tape and with the tape-head on the initial symbol of u. 

The Printing Problem for a given Turing machine M and given symbol S0 is the problem to determine of a given finite string u whether the symbol S0 will eventually occur on M’s tape when it is started with u on its tape and with the tape-head on the initial symbol of u. 

Of course, it is very well known that, for each of these problems, one can exhibit a Turing machine with respect to which it is algorithmically unsolvable. In this paper, Lucas discusses these problems and notes that, despite being of the same degree of unsolvability, these problems are different in the sense that an example can be given of a Turing machine with an unsolvable halting problem but a solvable printing problem and vice versa. I think it is worth noting that an unsolvability example for either of these problems can be transformed into one that is unsolvable with respect to the other by a very simple change in its defining instruction table. 

Thus, let M be a Turing machine with an unsolvable printing problem. We modify its instruction table in two steps, transforming it into a machine with an unsolvable halting problem.

(1) Fill in the table so there is a row for each pair q, S of a machine state and a symbol. These rows should be dummies that change nothing: they should just reprint S, and return to the same state q.

(2) Introduce a new halting state q0 and change the rows calling for the printing of S0 by making q0 the final symbol in those rows. 

Clearly, the modified machine will eventually halt with a given input just in case the original machine would have eventually printed S0 with that input.

The unsolvability of the Halting Problem has been frequently mentioned in the literature, usually credited to Turing. It has been called to my attention that the first occurrence of the actual words “halting problem” seems to have been in the treatment of it in my 1958 book [Computability and unsolvability, McGraw-Hill Series in Information Processing and Computers, McGraw-Hill, Inc., New York, 1958; MR0124208]. I would certainly not claim credit in that connection for doing anything more than thinking of a good name. As Lucas points out, the mathematical content was quite explicit in [S. C. Kleene, Introduction to metamathematics, D. Van Nostrand Co., Inc., New York, NY, 1952; MR0051790] published six years earlier. Lucas also notes that in [op. cit.], I wrote, “the unsolvability of essentially these problems was first obtained by Turing”.

In discussing A. M. Turing’s [ Proc. London Math. Soc. (2) 42 (1936), no. 3, 230– 265; MR1577030; correction, Proc. London Math. Soc. (2) 43 (1937), no. 7, 544–546; MR1575661], Lucas writes, “Turing’s notion of computation pays no attention to any halting behavior”. This is true, and the halting problem, as such, is certainly not to be found in [A. M. Turing, op. cit.]. However I think it is worthwhile to consider these matters in a wider context. When Turing set out to formulate a precise characterization of computability, he already had considerable interest in and experience with numerical computation, particularly with real numbers. He was particularly interested in methods for computing the zeros of the zeta function. So it was natural that when he sought a way to make precise the notion of algorithmic calculability, he would think of computable real numbers. His machines were started on an empty tape and intended to print on the tape an infinite sequence of 0’s and 1’s, thus defining a real number in the interval [0,1]. This was a natural choice for Turing, but an unfortunate one for the development of computability theory. He called machines that did print such a sequence circle free, and used Cantor diagonalization to show that the problem of determining whether a given machine (given by its instruction table) is circle free is undecidable. (Jack Copeland has suggested calling the problem of determining whether a given machine is circle free, SATIS. I think this is a poor choice because it invites confusion with SAT, the NP complete satisfiability problem which has been studied by so many researchers.) But this problem is of degree 0′′ as Lucas shows in detail, and so is unsuitable for proving the unsolvability of the Entscheidungsproblem—Turing’s goal. For that purpose, he very cleverly used the unsolvability of the circle free problem to prove the unsolvability of what I call:

Turing’s Printing Problem. To determine of a given Turing machine and a given symbol S0, whether that machine started on a blank tape would ever print S0.

Of course, as it stands, this does not furnish a single machine with an unsolvable printing problem as is done in [M. D. Davis, op. cit.]. But all is not lost. It can readily be seen, as a consequence of Turing’s Printing Problem, that Turing’s universal machine has an unsolvable printing problem: If we had an algorithm for determining whether the universal machine with a given input would eventually print S0, we could feed it the instruction table of a given machine (strictly its code) to determine whether that machine, started with a blank tape, would ever print S0.