8

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. – Sniper Clown Jul 3 '12 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 Jul 3 '12 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. – Nick R Aug 21 '14 at 3:25
2

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 :) – kbelder Aug 19 '14 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... ;-) – Niel de Beaudrap Aug 20 '14 at 3:02
3

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.

3

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.

2

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"

1

I detect a slight confusion about what exactly the halting problem is.

It is wrong to say that the halting problem is undecidable, as in "proof that the halting problem is undecidable". The halting problem was decided by Turing's proof that no such algorithm could exist. Using your own notation, Turing showed that no matter which "p" you choose, there will always be "q" for which "p" cannot decide if "q" halts. It is the status of the case-specific "q" that is not decidable, not the halting problem itself.

This is my first day on PSE, and I hope that did not sound snarky. It wasn't meant to.

In terms of the general philosophical implications of Turing's result, on one level it appears to be saying that some things (in arithmetic) are true just because they are, and for no "logical" reason. On another level, Turing's result seems to support the view that truth can be relative and not absolute.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.