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!
Your paper’s examination of Turing’s 1936 work raises an interesting parallel in how fundamental mathematical concepts become formalized. While analysing whether Turing explicitly proved the halting problem’s undecidability, you note how his work on the circle-free problem and symbol-printing problem led to our modern understanding. This connects to a theorem about mathematical behaviours emerging from fundamental properties – suggesting that certain concepts, like Turing’s original formulations, may resist direct proof precisely because they emerge from fundamental properties of the system itself.
This seems particularly relevant to your discussion of how the circle-free problem, while not Turing-equivalent to the halting problem, still provided the framework for understanding computational limits.
Very nice paper. Though, I personally think it is more urgent to discuss current issues than historical ones. However, current issues are interwind with the past. Halting problem and all other undecidability problems are highly connected to the very urgent issues of today: AI and the boundary of AI. The core is: programed computation vs. instance-specific computation. Seems this concept is very new, instance-specific computation. But it indeed can be traced to Turing’s a-machine. Kugel discussed this many decades ago. I have followed this line of thinking for many years and it is quite rewarding.
Richard S. Sutton and Andrew G. Barto were awarded the 2025 Turing Award yesterday for their pioneering contributions to the field of reinforcement learning.
In an interview with Cam Linke (https://www.youtube.com/watch?v=9_PepvnqIfU), Sutton emphasized that the core of reinforcement learning lies in learning from experience, a principle that Alan Turing had already put forward in 1947. He stated:
“Alan Turing talked about learning from experience, he was the first one to do it for machines that learn from experience, of course we’ve always had animals that learn from experience, but in his 1947 lecture to the London mathematical Society he has a line, what we want is a machine that learns from experience that was like the very first public presentation on AI period, that’s pretty incredible. »
This interview naturally reminded me of Turing’s 1936 paper. In fact, it was this very work that laid the foundation for his later research on artificial intelligence.
In this paper, Turing explores undecidability, revealing the relationship between universality (general) and specificity (specific). His work profoundly influenced AI methodologies, driving the shift from rule-based reasoning (from general to specific) to data-driven learning (from specific to general).
Today, while data-driven artificial intelligence has made remarkable technological advances, our understanding of these systems remains opaque, like a true “black box”. In my view, this is partly because Turing’s 1936 paper has yet to be fully understood.
This is why I believe that revisiting Turing’s 1936 paper is important today, …
The “Easter” of Thought: Rebooting Turing, Starting from Generative Construction
By Working Group on Reading Turing’s 1936 Paper, 2025/4/21
Today, technology has almost become the grammar of our era. But do we still remember what the person who first wrote this grammar—Turing—was truly concerned with?
In 1936, he proposed the concept of the Turing Machine, not merely as a computational model, but as an exploration of how the simplest forms can continuously generate complex and ordered structures. This is not an operational construction, but a generative construction ontology.
However, Turing’s original thinking was later simplified into the halting problem, and the Turing machine was reduced to an algorithmic tool with halting. We wish to reassert: Turing’s true concern was not when to halt, but how to generate.
This generative thinking has unexpectedly continued and amplified in today’s GPT (Generative Pre-trained Transformer) systems. GPT uses the most basic language rules as seeds to continuously unfold an infinitely potential text world.
From the Turing machine to GPT, we see that the generative logic, starting from a constructive ontology, has traversed nearly a century of technological evolution, still writing new chapters in language and thought.
We begin by sharing the first article as the starting point for our reflection: « The Historical Obscuration of the Halting Term: Turing’s Original Intention and Later Misreadings. »
We hope this reboot will be like a gentle ray of spring light, awakening a peaceful and profound awareness: that the way we understand the world is shaping the world we perceive.
In this age of information overload, perhaps the most precious thing is not more knowledge, but a clear awareness of our cognitive limitations — the very foundation for renewing our thinking.
Pingback: Did Turing ever halt? HPS Colloquium, Notre Dame, October 2025 | Joel David Hamkins
Hi Joel,
Unfortunately this paper has a critical error:
“we also find it incorrect to suggest […] that one will find there anything like the familiar self-referential argument for the undecidability of the halting problem.” [Ham25]
When you go thru your analysis of how Turing demonstrated the undecidability of “circle-free” you gave the anti-diagonal (β) argument, but that wasn’t actually the proof Turing finally concluded undecidability with. While it was his motivation, as the anti-diagonal certainly cannot be computable, he left a comment that something about that proof was unfulfilling:
“This proof, although perfectly sound, has the disadvantage that it may leave the reader with a feeling that “there must be something wrong” [Tur36]
You have proceed to the next page to find the proof Turing establishes certainty for undecidability, and that one is *very* similar to the classic self-referential halting proof. See, despite Turing envisioning all his machines as infinitely running, when constructing the direct diagonal (β’) he did expect to be able to successfully simulate the Nth computable number to the Nth digit of that number. In many regards this can be considered a “halt” of a subroutine, even if not described as such. And then the classic undecidable paradox does indeed arise when Turing considers the diagonal computation (𝓗) encountering itself while enumerating the computable numbers: If it decides itself a “satisfactory” machine, the diagonal computation gets caught in a loop trying to simulate itself to some Rth digit, but since that digit had never been defined in the diagonal algo, it cannot be found:
“the instructions for calculating the R(K)-th would amount to “calculate the first R(K) figures computed by 𝓗 and write down the R(K)-th”. This R(K)-th figure would never be found.” [Tur36]
Only after that very familiar paradox does Turing find undecidability irrefutably established. For some reason Salvador’s paper misses this as well. I know it’s hard to read, but the fundamentals of undecidability in computing was really only the first two pages of §8, everything after in his paper only builds on that result.
Thank you for this comment! I will take a deeper look and reflect on this.
Thanks for your consideration, I’m eager to hear the results of your reflection! I’m sure you’ll come to an agreement on that after reading the 2nd page of §8 a few times, maybe even just once will be enough! Although the typings for machine names are a bit messy/faded in most copies I’ve seen posted, and that does hinder comprehension.
After this, you may be prepared for my next proposition. There have been a spattering of people dissenting to the consensus understanding of the halting problem, and a few attempts at refuting it. Not really in academia mind you, heck Professor Eric Hehner (UofT Emeritus) avoided doing so for decades until after he was almost retired, in fear of his career …
But I’m the first to apply my result to Turing’s paper directly, and something deeply unexpected, even a bit miraculous came out of it. My decision paradox mitigation strategy, applied to the logical interface of the decision machine for “satisfactory” numbers, not only allowed for computing the direct diagonal of the computable numbers (β’) … it did so in a way that could NOT be used to compute an anti-diagonal (β)!
How could one even expect such a result?? It is not intuitive to propose that a direct diagonal computation could not be used to produce an anti-diagonal computation, at all. I certainly didn’t expect it. I developed my decision paradox mitigation strategy contemplating the basic halting problem, and only stumbled into this while applying those logical strategies directly to the arguments made in Turing’s paper.
To me, this is too good to not be true, at least on some level. Does this stay within computing and perhaps motivate us to start, for example, doing halting analysis on *all* our real world systems… I certainly hope so. Does it go so far as to refute Rice’s Theorem… pretty serious maybe. Might it end up in a critique of Gödel’s Incompleteness? That’s really outside my expertise at the moment tbh, so a very cool might.
If this does peak your interest, please drop me an email or perhaps schedule a video call … otherwise, this comment will be sitting here for any future interest as well.
How is it going Joel? Have you had any time to reflect on this?
I’ve been doing more work on refuting the problem of semantic paradoxes, and have come up with the concept of “Reflective Turing Machines” which I believe can enable deciders in subverting these theoretical barriers.
I can’t wait to share it with anyone interested in paradoxes 🙏
I have looked into this further, and I don’t agree with your analysis. In particular, this is not a “critical error” as you say. The argument that Turing provides in the section you point at, to my way of thinking, is not similar to the standard self-referential proof of the undecidibility of the halting problem. He rather argues like this: if circle-freeness were decidable, then we could create a program that did this: look over all programs in turn, and for the nth circle-free program, run it to find the nth output digit and print that. Then he argues that the resulting algorithm is impossible, since on the one hand, it is clearly circle free, but if it were the nth circle-free program, then at stage n of the algorithm itself, if would be left waiting to find its nth output digit before being able to give it. Contradiction. This is a nice argument, but it is not the same as the self-referential halting proof. I suppose that from a contemporary point of view, one can view it as the result of an attempt, under the assumption that circle-free is decidable, to produce a program that is circle-free if and only if it is not circle-free. However, Turing himself doesn’t present his argument this way.
Meanwhile, Tedy and I have added a brief mention of this argument to our paper.
Thank you for your continued engagement!
> However, Turing himself doesn’t present his argument this way.
Turing’s paper is not perfect, but I do think he realizes the inherent undecidability. I think he may have even realized it while considering the inverse diagonal computation (as it would occur there as well), and was surprised it also appeared in the direct diagonal… but didn’t write down his entire thought process (who can even!?)
Regardless of how Turing specifically worded his interpretation… you must consider it from an algorithmic point of view: as the diagonal computation is iterating across all possible machines, it must test each M machine for decidability with decision machine D. If D finds M unsatisfactory the diagonal computation skips over M. If D find M satisfactory it simulates M to the Nth appropriated digit, writing that digit down, and continuing to the next machine. The paradox occurs once that M is the diagonal computation itself:
– If D decides the diagonal computation as “satisfactory”, then the diagonal gets stuck in an unsatisfactory infinite loop trying to find a digit that doesn’t exist
– If D decides the diagonal computation as “unsatisfactory”, then the diagonal skips itself and proceeds in a satisfactory fashion.
Within the diagonal computation, D cannot seemingly decide on the diagonal computation accurately. Turing may not have worded it in that exact way, but the semantic paradox does exist within the algorithm Turing described, and it is that problem that convinces Turing to finally declare uncomputability/undecidability.
I call it a critical error because it’s important to understand the semantic undecidability (within computing) does actually stem from Turing’s original paper on computable numbers. Anyone trying to resolve the halting problem (there’s a few out there other than me) must actually address Turing’s original paper on the matter, which is fundamentally a more complex/problematic variation of semantic paradoxes, than the simple halting problem.
I do implore you to find a way to see eye to eye with me on this, I’m drifting out here in the depths of largely unrealized theory all alone for the most part 🙏🙏🙏
I disagree. To do the self-referential analysis, one would argue like this: Assume that circle-free is decidable. Design a machine N that on input M, a machine, and first checks whether M is circle free. If it is, then N should jump into an infinite circle. If it isn’t, then N should produce the digits of pi. In short, M has the opposite behavior as N in regard to being circle-free. Now, observe that M on input M will be circle-free if and only if it isn’t circle free.
This would be a true analogue of the self-referential argument. But it is basically absent in Turing 1936 in this succinct simple form. Yet this is the standard form we use today for the halting problem, the printing problem, and innumerable other problems. He just doesn’t have it.
Part of the problem is that he doesn’t actually have the concept of “input” to a machine, but only in the infinite processes, running on all possible natural number inputs. In contemporary lights, we can see how his ideas have the effect of running something like this argument, but to my way of thinking, the self-referential formulation is a genuine advance, which came later, even though Turing proved the undecidability of circle-freeness, as well as the undecidability of the printing problem.
> Design a machine N that on input M ….
Why does that machine N even need an input? The most basic form is simply a machine that checks itself whether it halts or not, and does the opposite of any decision made on the matter. Written in a typescript-ish pseudocode, this is one line:
const N = () -> if ( halts(N) ) loop_forever();
wikipedia has it in a more pythonish pseudocode:
https://en.wikipedia.org/wiki/Halting_problem#Proof_concept
The self reference is gunna exist in one of three ways: either it will be hard-coded into the machine (by ultimately a quine), or passed in via an input, or it will be found via an entire search of the machine possibility space … but it’s gunna be there one way or another. There seems to be this notion that the manner of finding the paradoxical, unclassifiable machine matters … but I really fail to see why.
> Part of the problem is that he doesn’t actually have the concept of “input” to a machine,
It’s true the diagonal computation H is iterating across all natural numbers, so it searches the entire machine possibility space to find the paradox … but the the decision machine D that operates internally to H does have a concept of input:
“a machine D which, when supplied with the S.D of any computing machine M …” [Tur36]
and output:
“if M is circular will mark the S.D with the symbol “u” and if it is circle-free will mark it with “s”” [Tur36]
he even invented a proto- memory stack frame to do D’s temporary computation in:
“We may suppose that [D] uses the E-squares [of the tape] beyond all symbols on F-squares, and that when it has reached its verdict all the rough work done by D is erased.” [Tur36]
When Turing was first imaging his machine’s operation, he divided up the tape into alternativing E and F squares (memory cells containing 1 symbol). F would contain the “output” of the machine at the end, while E contains all the temporary state that is not directly included in the “output” of the machine and may be thought of as being totally erased before machine end. Much like a modern stack frame, running D internally would do temporary work in E-squares beyond the last F-square. Which would ultimately be erased at some future point before the overall machine ends, much like what happens when stack frame is popped off say a C-type memory stack.
Note: This E/F-square notion wasn’t built into the fundamentals of a TM tape, but rather a convention he was using in the specific machine-descriptions/programs he wrote/described for it.
Tbh, the fact H (the diagonal machine computing across all “satisfactory” numbers) is iterating over *all* possible input machine descriptions to D and running them one by one, makes it a stronger problem of undecidability than N. N only creates one point of contradiction, D creates an infinite amount.
So while the named self-reference was an innovation in that it made it easier to understand, it’s also a weaker form of the undecidability problem.
> Turing proved the undecidability of circle-freeness, as well as the undecidability of the printing problem.
It’s also worth noting he based the printing problem undecidability on the undecidability of the “satisfactory”/circle-free problem, very much like what we more normally do with halting problem today. So he kinda started that trend too.