计算机理论中流行的一个最基本术语就是“停机问题”（the Halting Problem）【1】，其基本意思是：是否存在一个程序判断任给的一个程序在一个输入下，给出结果（停机），还是无限运行下去（不停机）
图灵于1936年发表了著名的论文"论可计算数及其在判定问题上的应用（On Computability Numbers, with an Application to the Entscheidungsproblem）”【2】，旨在解决由希尔伯特提出“Entscheidungsproblem（判定问题）”，由此奠定了计算机理论。
后来学术界认为图灵在1936年论文中处理的“判定问题”是“停机问题”，然而图灵在他的论文中从来没有用过“停机问题”这个术语，那么此术语从何而来？
已知最早使用 “停机问题”一词是在Martin Davis的一个证明中【3】（p.70-71）：
"Theorem 2.2 There exists a Turing machine whose halting problem is recursively unsolvable.
但是Davis在他的证明没有给出 “停机问题”术语的出处，所以人们推断这是他的原创。“The Essential Turing”一书的作者Jack Copeland这样说【4】（p.40)：
- The halting problem was so named (and, it appears, first stated) by Martin Davis. The proposition that the halting problem cannot be solved by computing machine is known as the ‘halting theorem’. (It is often said that Turing stated and proved the halting theorem in ‘On Computable Numbers’, but strictly this is not true.)
所以，我们的问题是：
- 为什么要用“停机问题”替代图灵1936年论文中的“判定问题”？
- “停机问题”与图灵1936年论文中的“判定问题”等价吗？
参考文献：
【1】https://en.wikipedia.org/wiki/Halting_problem
【2】Turing, A. M. (1937). "On Computable Numbers, with an Application to the Entscheidungsproblem". https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf
【3】Martin Davis (1958). Computability and Unsolvability. New York: McGraw-Hill.
【4】B. Jack. Copeland, The EssentialTuring, 2004.
http://www.cse.chalmers.se/~aikmitr/papers/Turing.pdf
转载本文请联系原作者获取授权，同时请注明本文来自柳渝科学网博客。
链接地址：https://wap.sciencenet.cn/blog-2322490-1383237.html?mobile=1
收藏
