Did Turing prove the undecidability of the halting problem?

2024/06/30 by Joel David Hamkins, Theodor Nenu, Hamkins, Joel David +1 · 5 voices · 1 citation
Computer Science · #Computability, Logic, AI Algorithms

paper · pdf · doi:10.48550/arxiv.2407.00680

Abstract

We discuss the accuracy of the attribution commonly given to Turing's 1936 paper "On computable numbers..." for the computable undecidability of the halting problem, coming eventually to a nuanced conclusion.

Cited by

• Undecidability of Finite Orbit Recognition in Polynomial Maps

Discussions

• Did Turing prove the undecidability of the halting problem? [hn, 81 points, 105 comments]
• My paper with Tedy Nenu on Alan Turing and the halting problem has now appeared. doi.org/10.1093/logc... [bsky, 7 points, 0 comments]
• #arXiv Did Turing prove the undecidability of the halting problem? arxiv.org/abs/2407.00680 "Turing proved taht the symbol-printing problem, to decide if a given program will ever print a given symbol [bsky, 2 points, 1 comments]
• Did Turing prove the undecidability of the halting problem? (arxiv.org) Main Link | Discussion [bsky, 0 points, 0 comments]
• # arXiv Did Turing prove the undecidability of the halting problem? https:// arxiv.org/abs/2407.00680 "Turing proved taht the symbol-printing problem, to decide if a given program will ever print a gi [mastodon, 0 points, 0 comments]

Related

• The Halting Paradox
• Is the Halting probability a Dedekind real number?
• The halting problem is decidable on a set of asymptotic probability one
• A note reviewing Turing's 1936
• Context-Dependent Functions: Narrowing the Realm of Turing's Halting Problem