HackerPapers

arXiv:2407.00680math.LO

Did Turing prove the undecidability of the halting problem?

Joel David Hamkins, Theodor Nenu

HN submission. Found in a submission link or body. Submitters do not count as commenters in the main ranking; a submission is not an endorsement.

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.

arXiv comments
19 pages. Commentary may be made on the first author's blog at https://jdh.hamkins.org/turing-halting-problem. Minor revisions in v2 and v3
Journal reference
DOI
Subjects
math.LOLogic cs.LOLogic in Computer Science

On Hacker News

No comments linking this paper were found in the collected sources. Found in 1 HN submission from Jul 2024 to Jul 2024. Open submission discussions.

Comments linking this paper, per year.

Discussed in comments0 threads

No comments linking this paper were found in the collected sources. Open submission discussions.

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.