In a great answer, a community member gave the following proof sketch that the halting problem is undecidable:

Proof that the halting problem is undecidable. If there were a computable procedure to reliably determine whether a given program/input halts, then design a new program q that on input p first asks whether p halts on input p, and then performs the opposite behavior itself. It now follows that q halts on input q if and only if it doesn't, a contradiction.

Following Mahmud's helpful link below, I found a wonderful article by what appears to be the same user on this subject. In addition, Wikipedia's entry on the problem was helpful in wrapping my head around this. (I also came across this amusing poem about the problem.) I think I understand the way in which this gives us 'unsolvable problems' for any Turing Machine and how a weak form of Godel's Incompleteness Theorem can be derived from the proof that the halting problem is undecidable.

What other, perhaps more general, implications of the undecidability of the halting problem might there be? (In particular, how if at all are these distinct from those of Godel's Incompleteness Theorem?)

  • 1
    Did you have anything specific in mind by philosophical implications? One can in theory perform hypercomputation and there is a mathematical question here. Commented Jul 3, 2012 at 5:42
  • @Mahmud The supertask implications are pretty interesting, and definitely in line with my question; one way to state the concern here is to simply unpack what implications might there be -- and also whether there is any significant difference between the halting problem's undecidability and Godelian incompleteness.
    – Joseph Weissman
    Commented Jul 3, 2012 at 18:38
  • If you accept the validity of the reductio ad absurdum method of proof, then a supertask can be shown to be logically impossible.
    – nwr
    Commented Aug 21, 2014 at 3:25
  • I think the implication is that reality is more complex than a simple algorithm or math proof?
    – Scott Rowe
    Commented Oct 3, 2022 at 12:23
  • This is a really, really good question. What does halt/continue mean exactly? Alan Turing is more than just a mathematician.
    – Hudjefa
    Commented Mar 5, 2023 at 10:39

4 Answers 4


With regards to your comment:

"... one way to state the concern [with respect to the Halting Problem] is to simply unpack what implications might there be ..."

One could say that the Halting Problem indicates that unpacking the implications of logical propositions is in principle only simple if you are lucky enough that the proposition itself is one with a simple structure. In any logical framework which is sufficiently complicated to be interesting, the fact of what the logical consequences are may not even exist, from a constructivist point of view.

The Halting Problem indicates that clever reasoning, using an understanding of the big picture and insight into the structure of a logical situation, some times is not enough. There is an infinite hierarchy of logical problems having subtler and subtler structure, receding to a horizon of problems which can scarcely be said to have structure at all; and so to resolve those problems, there exist no time-saving techniques — to find the answers, there is no recourse but brute force computation.

If you believe that the world is modeled well enough by logic that you're tempted to say that the world "seems logical", it follows that there are likely to be an infinite hierarchy of physical phenomena of increasing complexity, to the point where there will be incomprehensible phenomena about which we can scarcely form any intelligent ideas; where in the end the only thing there is to do is to watch them unfold with time.

  • Which saves the concept of free will :) Commented Aug 19, 2014 at 22:45
  • @kbelder: only if "unpredictability" is what you mean by freeness, and only if human behaviour is actually unpredictable. The very notions of "character" and "mood altering drugs" somewhat put the lie to that... ;-) Commented Aug 20, 2014 at 3:02

What you probably had in the mind is the Holy Grail of all mathematics and philosophy, the TOE or Theory of Everything proposed by Max Tegmark. Gregory Chaitin, who in his YouTube video sums up saying that the structure of mathematics is randomness, also concludes in his article Leibniz, Randomness & the Halting Probability that mathematics community may head towards "quasi-empirical" direction. In his words:

At any rate, that's the way things seem to me. Perhaps by the time we reach the centenary of Turing's death this quasi-empirical view will have made some headway, or perhaps instead these foreign ideas will be utterly rejected by the immune system of the math community. For now they certainly are rejected. But the past fifty years have brought us many surprises, and I expect that the next fifty years will too, a great many indeed.

Of coursere if there is no TOE and mathematics becomes an art of science of "quasi-empiricism" then famous open problems such as Riemann Hypothesis or Goldbach may not be provable. Chaitin concludes here:

Maybe, rather than attempting to prove results such as the celebrated Riemann hypothesis, mathematicians should accept that they may not be provable and simply accept them as an axiom.

  • 1
    As far as I know Max Tegmark has not claimed his TOE would lead to any new mathematical results, so although it would be a sort of philosophical unification of the physical world with the 'platonic' world of mathematical forms, I don't think it makes sense to call it a "holy grail of all mathematics".
    – Hypnosifl
    Commented Sep 23, 2022 at 16:40
  • BTW, Stephen Wolfram and his team seems to think homotopy type theory might be a clue towards a kind of unification of many different areas of math, see writings.stephenwolfram.com/2022/03/… along with the piece by Jonathan Gorard at wolframphysics.org/bulletins/2020/08/… (see the paragraph beginning 'The effort to formalize mathematics' and the next few)
    – Hypnosifl
    Commented Sep 23, 2022 at 16:42

One implication of the undecidability of the halting problem might be that it implies limits to our ability to know some conceptual truths a priori. See this paper by Martinez for some ideas about what this might look like.


According to Wikipedia Roger Penrose used the halting problem to argue that the human mind cannot be simulated with an algorithm (I did not find the original argument yet).

Roger Penrose "argues against the viewpoint that the rational processes of the mind are completely algorithmic and can thus be duplicated by a sufficiently complex computer. This contrasts with supporters of strong artificial intelligence, who contend that thought can be simulated algorithmically. He bases this on claims that consciousness transcends formal logic because things such as the insolubility of the halting problem and Gödel's incompleteness theorem prevent an algorithmically based system of logic from reproducing such traits of human intelligence as mathematical insight"

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .