Charles Petzold是《The Annotated Turing : A Guided Tour Through Alan Turing’s Historic Paper on Computability and the Turing Machine》(图灵注释：艾伦·图灵关于可计算性和图灵机的历史性论文导读，2008）一书的作者。
《图灵注释》简介
https://www.charlespetzold.com/books/
图灵机是一台虚构的（甚至不完全是假设的）计算机，由英国数学家艾伦·图灵（1912-1954）于 1936 年发明，用于帮助解决数学逻辑问题。作为副产品，图灵还创立了可计算性理论领域：研究数字计算机的能力和局限性。
本书介绍了图灵的原始 36 页论文（以及后续 3 页更正），并附有背景章节和大量注释，解释了图灵的许多陈述，阐明了他的讨论，并提供了大量示例。故事中交织着图灵自己迷人一生的亮点。
***
图灵与“停机问题”（Charles Petzold）
以下段落有什么问题？
Turing found that he could phrase his version of the question in terms of the problem of deciding whether or not the nth Turing machine would actually ever stop when acting on the number m. This problem was referred to as the halting problem.
— Roger Penrose，《皇帝的新脑》（牛津大学出版社，1989 年），第 57 页
将图灵与“停机问题”联系起来是一种时代错误。图灵在 1936 年的论文《论可计算数及其在判定问题中的应用》中最初提出了计算实数的机器的概念。由于实数（一般而言）具有无限多的位数，因此这些机器可以永远运行。如果机器进入非打印循环或进入不存在的格局，则将不再计算实数的位数，因此（用图灵的话来说）“不令人满意”。
即使图灵后来让他的机器计算函数（从某种意义上说，通用机器执行一项功能，但在他的论文第 10 节中，图灵描述了明确实现数论函数的机器），机器仍然会永远运行。函数机器计算 0、1、2 等参数的函数值，将整合结果编码为以 0 分隔的 1，但仍会永远运行。
随着图灵机的概念后来被推广并应用于可计算性问题，重新表述机器变得方便起来。这些重新表述的机器不再计算实数，而是计算数论函数的单个值，然后停机。令人满意的机器和不令人满意的机器被互换了：在这个新概念中，停机的机器是“好”机器，而不停机的机器则不是。
据斯蒂芬·克莱恩 (Stephen Kleene) 称，他从 1941 年开始在威斯康星大学 (University of Wisconsin) 的讲座中以这种方式重新表述了图灵机：
- While fully honoring Turing's conception of what his machines could do, I was skeptical that his was the easiest way to apply them in the computation of number-theoretic functions. — S.C. Kleene, "Origins of Recursive Function Theory," Annals of the History of Computing, Vol. 3, No. 1 (Jan. 1981), pg. 61
Martin Davis 认为，他最早在 1952 年开始在伊利诺伊大学的讲座中使用“停机问题”一词，与图灵机的类似重新表述有关。[B. Jack Copeland，《 Essential Turing》（Clarendon Press，2004 年），第 40 页，脚注 61] 该术语在 Davis 的著作《可计算性和不可解性》（McGraw-Hill，1958 年）中被广泛传播：
- Theorem 2.2. There exists a Turing machine whose halting problem is recursively unsolvable. [pg. 70]
撰写有关图灵机的文章的人最好在提及图灵最初关于机器的概念和后来的这些公式时更加清晰一些。我对即将出版的《The Annotated Turing 》一书的希望之一就是让更多人了解图灵最初的概念。这样我们就可以欣赏图灵机背后的丰富历史，以及它随后如何影响数学、可计算性、意识和宇宙学的思想。
原文：
https://www.charlespetzold.com/blog/2007/11/Turing-Halting-Problem.html
Turing and the Halting Problem
November 26, 2007New York, N.Y.
What is wrong with the following passage?
Turing found that he could phrase his version of the question in terms of the problem of deciding whether or not the nth Turing machine would actually ever stop when acting on the number m. This problem was referred to as the halting problem.
— Roger Penrose, The Emperor's New Mind (Oxford University Press, 1989), pg. 57
The association of Turing with the "halting problem" is an anachronism. Turing's original conception in his 1936 paper "On Computable Numbers, with an Application to the Entscheidungsproblem" was of machines that compute real numbers. Because real numbers (in general) have an infinite number of digits, these machines run forever. A machine that gets into a non-printing loop, or which enters a configuration that doesn't exist, will no longer compute digits of the real number and hence (in Turing's terms) is « unsatisfactory."
Even when Turing later lets his machines compute functions — in a sense, the Universal Machine performs a function, but in §10 of his paper, Turing describes machines that explicitly implement number-theoretic functions — the machines still run forever. The function machine calculates the function for an argument of 0, then 1, then 2, and so forth, encoding the integral results as runs of 1's separated by 0's, but still running forever.
As the concept of the Turing Machine was later generalized and applied to problems of computability, it became convenient to reformulate the machine. Instead of computing real numbers, these reformulated machines calculate a single value of a number-theoretic function and then halt. The satisfactory and unsatisfactory machines were swapped: In this new concept, machines that halted were "good" machines and machines that didn't halt were not.
According to Stephen Kleene, he reformulated the Turing Machine in this way in lectures he gave at the University of Wisconsin begnning in 1941.
While fully honoring Turing's conception of what his machines could do, I was skeptical that his was the easiest way to apply them in the computation of number-theoretic functions. — S.C. Kleene, "Origins of Recursive Function Theory," Annals of the History of Computing, Vol. 3, No. 1 (Jan. 1981), pg. 61
Kleene's reformulation first appeared in print in Chapter XIII of his book Introduction to Metamathematics (Van Nostrand, 1952). Martin Davis believes that he first started using the term "halting problem" in connection with a similar reformulation of Turing Machines in lectures at the University of Illinois beginning in 1952. [B. Jack Copeland, The Essential Turing (Clarendon Press, 2004), pg. 40, footnote 61] The term was released into the wider world in Davis's book Computability and Unsolvability (McGraw-Hill, 1958):
Theorem 2.2. There exists a Turing machine whose halting problem is recursively unsolvable. [pg. 70]
It would be best for people writing about the Turing Machine to exercise a little more clarity in referring to Turing's original conception of his machines and these later formulations. One of the hopes I have for my forthcoming book The Annotated Turing is to make Turing's original conception better known. We can then appreciate the richness of the history behind the Turing Machine and how it has subsequently influenced ideas about mathematics, computability, the consciousness, and cosmology.
转载本文请联系原作者获取授权，同时请注明本文来自柳渝科学网博客。
链接地址：https://wap.sciencenet.cn/blog-2322490-1460805.html?mobile=1
收藏
