“Did Turing prove the undecidability of the halting problem?”（图灵是否证明了“停机问题”的不可判定性？）的作者Joel David Hamkins是英国牛津大学逻辑学教授，Theodor Nenu是英国牛津大学哲学讲师，在此文中作者详细探讨了“停机问题”的起源。

题目：图灵是否证明了“停机问题”的不可判定性？(Joel David Hamkins and Theodor Nenu, 2024)

摘要。我们讨论将停机问题的可计算不可判定性归因于图灵（1936 年）的准确性，最终得出了一个微妙的结论。

停机问题是确定给定计算机程序是否在给定输入时停止的判定问题，众所周知，该问题具有计算不可判定性。在可计算性理论文献中，人们经常发现该结果归因于艾伦·图灵 (1936)，我们想考虑一下这些归因的准确性。毕竟，停机问题这个术语、该问题的现代表述以及其不可判定性的常见自指证明，严格来说，在图灵的著作中都没有出现。然而，图灵确实引入了不可判定问题的概念，证明了他所谓的无环问题（circle-free）是不可判定的，随后也证明了我们所谓的符号打印问题（即确定给定程序是否会打印给定符号）是不可判定的。后一个问题很容易看出与停机问题在计算上等价，并且可以在各种情况和应用中代替停机问题——它们很容易相互转换。此外，图灵还提出了一个广泛的思想框架，足以用于停机问题的当代分析，包括：图灵机的定义；用数字标记程序，以便可以枚举程序并将其作为其他程序的输入；通用计算机的存在；几个问题的不可判定性，与停机问题一样，以其他程序作为输入，包括无环问题、符号打印问题和无限符号打印问题，以及希尔伯特-阿克曼判定问题。鉴于这些事实，并考虑到一些普遍的文化观察，数学归因通常不仅严格针对原始作品的确切内容，而且在许多情况下还慷慨地针对这些想法直接产生的进一步的综合见解，最终我们认为将停机问题的不可判定性有条件地归因于图灵并不为过。话虽如此，我们也认为建议在图灵 (1936) 中找到有关停机问题的讨论或其不可判定性的证明是不正确的。

参考文献：

Joel David Hamkins and Theodor Nenu, Did Turing prove the undecidability of the halting problem? （2024）

https://arxiv.org/pdf/2407.00680