“The origins of the halting problem”的作者Salvador Lucas是西班牙的瓦伦西亚理工大学 (Universitat Politècnica de València) 计算机系的教授，在此文中作者详细探讨了“停机问题”的起源，指出“停机问题”既不是图灵在1936年论文中提出的，也不是图灵关心的议题。然而，学术界的“标准故事”却把“停机问题”强加在图灵1936年这篇具有里程碑意义的论文上，。。。
“停机问题”溯源
摘要
停机问题是不可判定问题的一个突出例子，它的提出和不可判定性证明通常归功于图灵 1936 年发表的里程碑式的论文。不过， 科普兰（Copeland） 在 2004 年注意到，这个问题的命名，显然是在马丁-戴维斯（Martin Davis）1958 年的一本书中首次提出的。我们还提供了以下支持这一说法的部分论据： (i)图灵关注的是具有无限多位数的可计算（实数）数（如π），在他的论文中，图灵并不关注停机机器；(ii)图灵考虑的两个判定问题涉及他的机器产生特定类型输出的能力，而不是达到停机状态，图灵的计算概念中缺少这一点；(iii)从 1936 年到 1958 年，在考虑该领域的文献时，没有一篇论文提到图灵机的任何 “停机问题”，直到戴维斯的书。不过，(iv) 丘奇（Church）和(v) 克莱因（Kleene）做出了重要的初步贡献，对丘奇来说，终止是他的计算概念（λ-计算）的一部分，而克莱因（Kleene）在其 1952 年的著作中基本上提出了我们现在所知的停机问题。
The origins of the halting problem
Abstract
The halting problem is a prominent example of undecidable problem and its formulation and undecidability proof is usually attributed to Turing's 1936 landmark paper. Copeland noticed in 2004, though, that it was so named and, apparently, first stated in a 1958 book by Martin Davis. We provide additional arguments partially supporting this claim as follows: (i) with a focus on computable (real) numbers with infinitely many digits (e.g., π), in his paper Turing was not concerned with halting machines; (ii) the two decision problems considered by Turing concern the ability of his machines to produce specific kinds of outputs, rather than reaching a halting state, something which was missing from Turing's notion of computation; and (iii) from 1936 to 1958, when considering the literature of the field no paper refers to any “halting problem” of Turing Machines until Davis' book. However, there were important preliminary contributions by (iv) Church, for whom termination was part of his notion of computation (for the λ-calculus), and (v) Kleene, who essentially formulated, in his 1952 book, what we know as the halting problem now.
参考文献：
Salvador Lucas, The origins of the halting problem,
https://www.sciencedirect.com/science/article/pii/S235222082100050X
转载本文请联系原作者获取授权，同时请注明本文来自柳渝科学网博客。
链接地址：https://wap.sciencenet.cn/blog-2322490-1459061.html?mobile=1
收藏
