22
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Welcome to Computer Science Stack Exchange. Please read cs.stackexchange.com/tour.if you have not yet done so. --- What did you try for a more powerful model than TM? What is blocking you? $\endgroup$
    – babou
    Jul 26, 2015 at 22:12
  • 2
    $\begingroup$ @babou On the contrary, you need a less powerful model. $\endgroup$
    – Yuval Filmus
    Jul 26, 2015 at 22:15
  • 2
    $\begingroup$ @YuvalFilmus Well, the OP is asking for a more powerful model, not a weaker one. --- with apologies to H2CO3 ... My question was actually a joke as it is a standard question when people submit their homework as question. It was of course not appropriate here, as no one is expecting you would find such a model. I hope you will not take it too acidly. $\endgroup$
    – babou
    Jul 26, 2015 at 23:11
  • 1
    $\begingroup$ You might like to read about Hypercomputation en.wikipedia.org/wiki/Hypercomputation . $\endgroup$
    – Eric Towers
    Jul 27, 2015 at 17:29

5 Answers 5

Reset to default
16
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Assuming ZFC is consistent, it's still incomplete i.e. there are sentences that we can neither proves nor disproves from ZFC, and this is intimately related with halting problem being unsolvable, if halting were solvable we could prove or disprove all sentences. This is math, and this is not a inconsistency to be solved but also a theorem (Gödel) $\endgroup$
    – Hernan_eche
    Jul 28, 2015 at 15:02
  • $\begingroup$ @Hernan_eche Well ... yes and ... what...? If you think that inconsistency is not worse than incompleteness, that is your personnal judgement. I doubt most mathematicians would agree. You may not like TM that do not terminate. But would you like them better to terminate always, saying sometimes yes and sometimes no, on the same input. What would you make of the answer? And if you think non-determinism ... think twice. $\endgroup$
    – babou
    Jul 28, 2015 at 15:49
  • $\begingroup$ I've comment just to put it clear that Computer Science and Math fight same problems, to avoid readers to misinterpret the answer as if math were solved its foundation problems with ZFC and halting problem were just a computer science problem, that's not the case, there is a one to one correspondence between incompleteness and halting problem, it's the same issue. I don't think incompleteness being worse or better than inconsistency, but I think incompleteness will become inconsistency if you want to build higher order systems. $\endgroup$
    – Hernan_eche
    Jul 28, 2015 at 16:07
18
$\begingroup$

Well, you can always consider a Turing machine equipped with an oracle for the ordinary Turing machine halting problem. That is, your new machine has a special tape, onto which it can write the description of an ordinary Turing machine and its input and ask if that machine halts on that input. In a single step, you get an answer, and you can use that to perform further computation. (It doesn't matter whether it's in a single step or not: it would be enough if it was guaranteed to be in some finite number of steps.)

However, there are two problems with this approach.

  1. Turing machines equipped with such an oracle can't decide their own halting problem: Turing's proof of the undecidability of the ordinary halting problem can easily be modified to this new setting. In fact, there's an infinite hierarchy, known as the "Turing degrees", generated by giving the next level of the hierarchy an oracle for the halting problem of the previous one.

  2. Nobody has ever suggested any way in which such an oracle could be physically implemented. It's all very well as a theoretical device but nobody has any clue how to build one.

Also, note that ZFC is, in a sense, weaker than naive set theory, not stronger. ZFC can't express Russell's paradox, whereas naive set theory can. As such, a better analogy would be to ask whether the halting problem is decidable for weaker models of computation than Turing machines. For example, the halting problem for deterministic finite automata (DFAs) is decidable, since DFAs are guaranteed to halt for every input.

Improve this answer
$\endgroup$
3
  • $\begingroup$ I think that its own halting problem is is solvable by any family of automata iff it is trivial, that is either they all halt or none of them does (which may be considered as strange in this case). $\endgroup$
    – babou
    Jul 26, 2015 at 23:06
  • 1
    $\begingroup$ @babou: what about automata where machine 0 loops forever, machine 1 outputs FALSE if its input is 0 else outputs TRUE and then halts. All other machines output FALSE and then halt. Is that a family of automata in which program 1 solves the non-trivial halting problem? Or is this not even an automaton family, on account of lacking some property, e.g. any kind of composition? $\endgroup$
    – Steve Jessop
    Jul 27, 2015 at 1:02
  • $\begingroup$ @SteveJessop Well, you (and Davis Richerby) are probably right in a sense. What bothers me is that this is a contrived example. You build a very weak family such that one machine in the family happens to be a halting decider for the whole family. But, as you suspect yourself (cf your remark about composition), there may be some basic closure property that is missing so that the problem can be trivialised. I do not have a ready answer, and I do agree that my remark needs more qualification as to what constitute a family of automata, but your counter-example leaves me unconvinced. $\endgroup$
    – babou
    Jul 27, 2015 at 14:03
2
$\begingroup$

Warning: A philosophical / non-rigor answer

This might get a little bit "philosophical", but I think it fits the spirit of your question.

A non-repeatable machine

A corner stone of the proof of the halting problem is that a Turing machine behaves like a function: For the same input it always gives the same output. If you remove this property, you don't have to deal with the "general" halting problem, in the sense that the machine can discover its own properties. But you also loose a lot of the desirable theoretical properties of such a machine.

Removing properties

It's a little bit like going from set theory to category theory: You loose some of the "paradoxons" by losing the limitations. But the result is much more difficult to handle.

In this case it means: You would have no idea if the machine presents you the "correct" result. As soon as you can always decide which result is correct, you have to deal with some kind of "halting problem" by applying the machine to itself and construct a contradiction. So such a machine would probably not be very useful.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Thank you, that "non-repeatable machine" thing sounds quite interesting, actually. I don't feel myself competent enough to comfortably say some wisdom about clever self-inspecting programs (because my gut instinct is that they are still expressible as Turing machines), but I feel they may very well be useful for some set of problems. $\endgroup$
    – H2CO3
    Jul 27, 2015 at 21:35
  • 1
    $\begingroup$ How would give an example of non repeatability? An how would you define halting in that case. A major difficulty is that, when you try to define strange computation model, usually gedanken ones, you have to define the meaning of halting, and what kind of input the deciding machine is supposed to analyze, and possibly a few other non trivial things. See for example the case of non-determinism. Not to mention the issue of what may be considered a computational model (probably not an ad hoc collection of machines). $\endgroup$
    – babou
    Jul 28, 2015 at 10:49
  • 1
    $\begingroup$ @H2CO3 A non-repeatable machine is only a kind of "Gedanken experiment" on what property you have to sacrifice to get out of the "general halting problem" (constructing a contradiction by letting the machine inspect itself). You will get a machine that is sometimes right, but you don't know when. It's like the program that calculates the lottery numbers for next week. I can easily provide you such a program. The hard part is for you to decide, which one of the many programs I will give you is the correct one... $\endgroup$
    – stefan.schwetschke
    Jul 28, 2015 at 11:53
2
$\begingroup$

The Halting Problem was not formulated to express the limitations of Turing Machines, but rather to express a limitation of all logic systems which can be expressed using a finite number of symbols. Once a logic system has the ability to express the solutions to problems of certain complexity, it will also have the ability to express problems it can't solve. Any extension of a logic system sufficient to express solutions to all of the problems it couldn't solve before will also include the ability to express new problems it can't solve.

Given any particular "Enhanced Turing Machine" specification, it would be possible to specify a "Super-Enhanced Turing Machine" which could examine a program for the ETM and report whether it would halt, but the SETM would only be able to analyze programs for the ETM--it wouldn't be able to analyze SETM programs. There's no way to define a machine that can analyze programs for itself and determine whether they halt because the act of adding new features would create new requirements for a self-analyzer, and there's no way to make the features "catch up" to the requirements.

Improve this answer
$\endgroup$
0
$\begingroup$

Such machines have been envisioned, and are called super-Turing machines. Several major classes of super-turing machine are

  • Real number machines (i.e. analog computers)
  • Turing machines given infinite time
  • Nondeterministic turing machine

Not all super-turing machines can solve the halting problem (Nondeterminnistic turing machines, in particular, cannot). However, the conceptual machines have been created, at least in thought experiments.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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