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*