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

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?

Answer

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.

Attribution
Source : Link , Question Author : H2CO3 , Answer Author : babou

Leave a Comment