Could the Halting Problem be "resolved" by escaping to a higher-level description of computation?

Problem Detail: 

I've recently heard an interesting analogy which states that Turing's proof of the undecidability of the halting problem is very similar to Russell's barber paradox.

So I got to wonder: mathematicians did eventually manage to make set theory consistent by transitioning from Cantor's naive formulation of the field to a more complex system of axioms (ZFC set theory), making important exclusions (restrictions) and additions along the way.

So would it perhaps be possible to try and come up with an abstract description of general computation that is more powerful and more expressive than Turing machines, and with which one could obtain either an existential proof or maybe even an algorithm for solving the halting problem for an arbitrary Turing-machine?

Asked By : H2CO3

Answered By : babou

You cannot really compare. Naive set theory had paradoxes that were eliminated by ZFC set theory. The theory has to be improved for consistency, as a basic assumption of scientific work is that consistency is achievable (else reasonning becomes a chancy business). I suppose mathematicians expected it had to be possible, and worked to resolve the issue.

There is no such situation with computation theory and the halting problem. There is no paradox, no inconsistency. It just so happens that there is no Turing machine that can solve the TM halting problem. It is simply a theorem, not a paradox.

So it may be that some breakthrough in our understanding of the universe will lead to computation models beyond what we can envision now. The only such event, in a very weak form, that remains within the TM realm, was possibly quantum computing. Other than this very weak example that touches complexity (how long does it take?) rather than computability (is it feasible?), I doubt anyone on this planet has a clue that computability beyond TM is to be expected.

Furthermore, the halting problem is a direct consequence of the fact that Turing machines are describable by a finite piece of text, a sequence of symbols. This is actually true of all our knowledge (as far as we know), and that is why speech and books are so important. This is true of all our techniques to describe proofs and computations.

So even if we were to find a way to extend the way we compute, say with the T+ machines. Either it would mean that we have found a way of expressing knowledge beyond writing finite document, in which case the whole thing falls out of my jurisdiction (I claim absolute incompetence) and probably anyone else's. Or it would still be expressible in finite documents, in which case it would have its own halting problem for T+ machines. And you would be asking the question again.

Actually that situation does exists in reverse. Some types of machines are weaker than Turing machines, such as Linear Bounded Automata (LBA). They are quite powerful though, but it can be shown exactly as it is done for TM that LBA cannot solve the halting problem for LBA. But TM can solve it for LBA.

Finally, you can imagine more powerful computational models by introducing oracle, that are devices that can give answers to specific problems, and can be called by a TM for answers, but unfortunately do not exists physically. Such oracle-extended TM is an exemple of the T+ machine I considered above. Some of them can solve the TM halting problem (abstractedly, not for real), but cannot solve their own Halting problem, even abstractedly.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/44763