Joel David Hamkins and Theodor Nenu, “Did Turing prove the undecidability of the halting problem?”, 18 pages, 2024, Mathematics arXiv:2407.00680.
Abstract. We discuss the accuracy of the attribution commonly given to Turing (1936) for the computable undecidability of the halting problem, eventually coming to a nuanced conclusion.
The halting problem is the decision problem of determining whether a given computer program halts on a given input, a problem famously known to be computably undecidable. In the computability theory literature, one quite commonly finds attribution for this result given to Alan Turing (1936), and we should like to consider the extent to which these attributions are accurate. After all, the term halting problem, the modern formulation of the problem, as well as the common self-referential proof of its undecidability, are all—strictly speaking—absent from Turing’s work. However, Turing does introduce the concept of an undecidable decision problem, proving that what he calls the circle-free problem is undecidable and subsequently also that what we call the symbol-printing problem, to decide if a given program will ever print a given symbol, is undecidable. This latter problem is easily seen to be computably equivalent to the halting problem and can arguably serve in diverse contexts and applications in place of the halting problem—they are easily translated to one another. Furthermore, Turing laid down an extensive framework of ideas sufficient for the contemporary analysis of the halting problem, including: the definition of Turing machines; the labeling of programs by numbers in a way that enables programs to be enumerated and also for them to be given as input to other programs; the existence of a universal computer; the undecidability of several problems that, like the halting problem, take other programs as input, including the circle-free problem, the symbol-printing problem, and the infinite-symbol-printing problem, as well as the Hilbert-Ackermann Entscheidungsproblem. In light of these facts, and considering some general cultural observations, by which mathematical attributions are often made not strictly for the exact content of original work, but also generously in many cases for the further aggregative insights to which those ideas directly gave rise, ultimately we do not find it unreasonable to offer qualified attribution to Turing for the undecidability of the halting problem. That said, we also find it incorrect to suggest that one will find a discussion of the halting problem or a proof of its undecidability in Turing (1936).
Read the full paper at the mathematics arxiv:2407.00680. (pdf download available)
Bibliography
- A. M. Turing. On Computable Numbers, with an Application to the Entscheidungsproblem. Proceedings of the London Mathematical Society 42.3 (1936), pp. 230–265. doi:10.1112/plms/s2-42.1.230.
Pingback: 图灵证明了停机问题的不可判定性吗？ - 偏执的码农
This is a very nice paper, yet it remains unclear whether Turing would have endorsed Martin Davis’s “halting problem” (e.g., in connection with computing, broadly construed). For more history, please consider having a look at:
https://www.dijkstrascry.com/lecture3
Purely technically, I would like to suggest that there is (actually) more than one way to go from Turing’s a-machines to halting machines. Davis only gave us one way, and there is (again) no reason to believe that Turing was not more open minded about the issue at hand. Please consider perusing these results: https://www.dijkstrascry.com/RBM
Yes, this is a question we cannot avoid if we want to understand Turing’s 1936 paper in depth:
– Whether Turing would have endorsed Martin Davis’s “halting problem” ?
I think that to answer this question, on the one hand, we need to revisit Turing’s original paper in 1936, and listen to what Turing said, instead of being satisfied with listening to others say what Turing said.
On the other hand, we need to listen to Davis’s explanation of why he used the “halting problem” to replace the “decision problem” that Turing dealt with.
Thanks for this contribution to the understanding of Turing’s 1936 paper. In 2021 I published a journal paper specifically addressing the halting problem and discussing a number of points that I also find in your paper. You can download the (open access) paper here: https://doi.org/10.1016/j.jlamp.2021.100687. I hope you will find it interesting or complementary to your own research. Of course any comment on your side will be welcome! Best regards, Salvador.
Yes, we came to know of your paper after we placed our paper on the archive and we are now citing you in our updated version of our paper (not yet released), since clearly there is some important overlap. Thank you for this comment!
Here’s a critical assessment of Strachey’s reductio ad absurdum proof: https://www.dijkstrascry.com/DaylightStrachey
Strachey makes no sense from an informed logic-engineering background.
I’d like to refer to Dale Jacquette’s critique of Turing in: “Computable Diagonalizations and Turing’s Cardinality Paradox” (2014), J. Gen. Philos. Sci. I’m hoping someone of Hamkins’s caliber will thoroughly engage with Jacquette and explain why he is wrong/right in disagreeing with Turing. (I’m sure nobody disagrees with Turing’s genius and impact. I speculate that 99% of my peers fail to understand Turing 1936, and I’m no exception. That, if valid, is an interesting sociological topic of research.)
There are also primary sources suggesting that Turing got some important parts of his 1936 UTM notion from his contemporaries. He did not just sit under a tree and invent everything from scratch — a claim often made in the 1980s.
There are two papers by the Greek scholar,
Doukas Kapantais, that not only claim to refute the Church-Turing Thesis (while abiding by Hilbert’s program), they have also been mentioned in the comm. of the acm — by Copeland and Shagrir (if I recall correctly).
For the sources, please scroll down on Kapantais’s website:
https://academyofathens.gr/en/personel/doykas-kapantais
Perhaps someone on this list is willing to invest time in studying this work. I’m sure Turing would have been thrilled by these potential developments.
I think that what you said is not an exaggeration. In fact 99% of my peers have not read Turing’s original paper in 1936, or some tried to read it, but gave up because they encountered difficulties and were unwilling to spend further time, …
Yes, « That, if valid, is an interesting sociological topic of research ». I would like to say, that is also an incredible academic event. . .
I forgot to confirm my contact information. Sorry. I do it now. Salvador.
Interesting work!
Your work confirms, through a revisiting of Turing’s 1936 paper and a detailed literature survey, that the « halting problem » was not proposed by Turing in his 1936 paper; but finally you said:
– ultimately we do not find it unreasonable to offer qualified attribution to Turing for the undecidability of the halting problem.
My question is:
– Since the halting problem is essentially no different from the decision problem dealt with by Turing, why didn’t Turing use this simpler notion of « halting », but instead used much more complex notions such as « computable number/sequence » and « circle-free machine » to define the core concept in computability theory, « computability »?
Well, I think the equivalence between the printing problem and the halting problem is quite clear from a contemporary perspective. But even so, Turing’s proof of the undecidability of the printing problem is not at all how we would typically prove this today, since his argument goes through the undecidability of the circle-free problem, which is not even Turing equivalent to the halting problem. So I think the explanation is that these ideas were not all very clear–they are difficult and in some cases profound—and it was in fact the genius of Turing to bring them to light in the first place. But he did so only imperfectly, as we can see looking back on it from our current understanding. But that understanding was possible only because of Turing’s achievement.
Happy New Year 2025 to everyone!
« I think the equivalence between the printing problem and the halting problem is quite clear from a contemporary perspective. But even so, Turing’s proof of the undecidability of the printing problem is not at all how we would typically prove this today, since his argument goes through the undecidability of the circle-free problem, which is not even Turing equivalent to the halting problem. »
I completely agree with your comment, which to me reflects the general confusion about understanding Turing’s 1936 paper.
Thank you so much for the opportunity to discuss this issue openly, especially in today’s world where the boom in artificial intelligence is revealing the challenges that humans must face in understanding ourselves!
Happy New Year 2025 to everyone!
« I think the equivalence between the printing problem and the halting problem is quite clear from a contemporary perspective. But even so, Turing’s proof of the undecidability of the printing problem is not at all how we would typically prove this today, since his argument goes through the undecidability of the circle-free problem, which is not even Turing equivalent to the halting problem. »
I completely agree with your comment, which to me reflects the general confusion about understanding Turing’s 1936 paper.
Thank you so much for this opportunity to discuss this issue openly, especially in today’s world where the boom in artificial intelligence is revealing the challenges that humans must face in understanding ourselves!