停机问题（1）- 术语溯源

“停机问题”（the Halting Problem）【1】是计算机理论中流行的一个最基本术语，现在学术界一致认为图灵在1936年论文“论可计算数及其在判定问题上的应用（On Computability Numbers, with an Application to the Entscheidungsproblem）”中处理的“判定问题”（Entscheidungsproblem）就是“停机问题”，然而图灵在他的论文中从来没有用过“停机问题”这个术语，那么此术语从何而来？


已知最早使用 “停机问题”一词是在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


 

Commentaires

Enregistrer un commentaire

Posts les plus consultés de ce blog

令人不安的哥德尔证明 - 倡议重读哥德尔1931年论文

美国最大出版社诺顿公司在介绍 2021 年出版的哥德尔传记 “ 理性的边缘之旅 - 库尔特 - 哥德尔的一生 ” （ Stephen Budiansky ）时说  [1]  ： 这是第一本为普通读者撰写的关于这位逻辑学家和数学家的重要传记，他的不完备性定理帮助发起了一场现代科学革命。库尔特 - 哥德尔（ Kurt Gödel ）的著名证明，即每个数学系统都必须包含 “ 为真但不可证明的命题 ”—— 在发表后的近一百年里，继续令数学、哲学和计算机科学感到不安。 此说并不夸张，那么哥德尔不完备性定理中到底有什么令人至今不安？如果我们仔细观察，就会发现这种不安并不是 因为哥德尔给出的 形式系统不完备性的 结论，也不是因为 哥德尔在证明中运用了 “ 说谎者悖论 ”，而是 哥德尔 将”自己说自己是不可证明的“ 说谎者悖论 命题当作 形式系统中正常的 “ 不可判定命题 ”了，由此 得出 形式系统中存在如 说谎者悖论 的命题是常态 ！ [2]  哥德尔的证明自发表以来一直受到挑战， 道森（ John W. Dawson Jr. ） 在文章 “ 哥德尔不完备性定理的接受情况（ The reception of Gödel's Incompleteness Theorems）” 中对此进行了梳理  [3]  （ p.74-95 ）： 策梅洛（Ernst Zermelo） 在 1931 年写给哥德尔的信中说，哥德尔对不可判定命题存在性的证明存在一个 “essential gap” ； 逻辑学家佩雷曼（ Chaïm Perelman） 断言，哥德尔发现的实际上是一个二律背反（Antinomy）； 维特根斯坦（Ludwig Wittgenstein）对哥德尔的证明发表了备受争议的评论（ Remarks on the Foundations of Mathematics ， 1938) ； 罗素（Bertrand Russell）在给 亨金（Leon Henkin）的信中表达了他的深刻困惑：我当然意识到哥德尔的工作具有根本的重要性，但我对它感到困惑。 [……] 如果一个给定的公理集导致矛盾，很明显，至少有一个公理必须是错误的。 。。。 还有 埃尔布朗（ Jacques Herbrand）在 1931 年写给哥德尔的信中指出  [4]...
Lire la suite

图灵谁如何定义“可计算性”的？

  I. How did Turing define the computability? Turing's 1936 paper, as its title suggests:  On Computable Numbers, with an Application to the Entscheidungsproblem , aimed to solve the  Entscheidungsproblem  proposed by Hilbert based on c omputable numbers .   Turing answered the Entscheidungsproblem negatively, Turing said: I propose, therefore, to show that there can be no general process for determining whether a given formula A of the functional calculus K is provable (Note: K refers to the first-order predicate), i.e. that there can be no machine which, supplied with any one A of these formulae, will eventually say whether A is provable. Therefore, Turing gave a definition of  decision problem  such that «  there is a general process for determining . . . ».   1. Decision problem     Turing said ([ 1], Section 8) : The expression ''there is a general process for determining . . .'' has been used throughout this section ...
Lire la suite

停机问题（3）- 证明溯源

  There are two versions of the popular proof of the "haling problem": one based on the liar's paradox and the other based on the Cantor’s diagonisation. The academic claims that the halting problem and its proofs are originated from Turing's 1936 paper, which is highly questionable, … Roger Penrose gave an accessible presentation of the proof of the halting problem based on the Cantor’s diagonisation in  The Emperor's New Mind , and I excerpt the relevant content as follows (p.59-64) : A natural question arises: how are we to decide whether or not any particular Turing machine (when fed with some specific input) will ever stop?  … So, is there some algorithmic procedure for answering the general question - the halting problem - completely automatically?  Turing showed that indeed there is not. His argument was essentially the following.  We first suppose that, on the contrary, there is such an algorithm. Then there must be some Turing machine H which 'decides...
Lire la suite