What are the philosophical implications of the Halting Problem?

Question

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?)

Answer 1

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.

Answer 2

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.

Answer 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.

Answer 4

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"