What problem does the halting problem solve in computing, whether theoretical or practical?

It is very easy to debug code which loops forever, just signal the debugger to break if the program is running for too long? What purpose / good is the halting problem? Why was Turing praised for it?

  • 7
    $\begingroup$ Just in case, a problem does not solve a problem. $\endgroup$ – Tsuyoshi Ito Oct 3 '12 at 22:20
  • 1
    $\begingroup$ I don't understand the complaint. Before you ship out software, don't you want to make sure it doesn't loop forever/time out? It's no good for the user if his program loops for a long while, and times out - they're not going to want to start debugging. Undecidability of the halting problem says that there is no single general method that decides if any given piece of code is sound on any given input. How is that not a useful thing? $\endgroup$ – Sasho Nikolov Oct 4 '12 at 4:29
  • 2
    $\begingroup$ The Halting Problem is not a solution, as its name states its a problem. $\endgroup$ – Jodrell Oct 4 '12 at 8:05
  • 1
    $\begingroup$ How do you know it wasn't about to finish on its own when you killed it for "running too long"? $\endgroup$ – OrangeDog Oct 4 '12 at 8:45
  • 1
    $\begingroup$ Actually a problem may be a solution. Think of women as a solution to the problem: men can't give birth to other men. $\endgroup$ – Erik Burigo Oct 4 '12 at 10:48

The halting problem is an example of a problem that a computer cannot solve. On the face of it, it might seem that computers can do anything, given enough resources and time. However, Turing showed that this intuition is false. Later on this was made more tangible by showing that a computer cannot decide whether a given Diophantine equation has solutions in the positive integers.

This is similar to Gödel's incompleteness theorem, which shows that the axiomatic method doesn't provide an answer to all possible questions. In fact, no finite list of axioms is enough to determine the truth of every statement regarding the natural numbers. Later on, a natural example emerged in the realm of set theory, namely the continuum hypothesis.


Just an extended (informal) comment.

As explained in Yuval's answer the halting problem is not computable.

But even if you were able to connect a Turing machine to a black-box (oracle) that solves it (i.e. the Turing machine sends a program $M$ and an input $x$ to the black-box and receives an answer whether $m$ halts on $x$ or not), you'll soon be in trouble again because the device TM+HALT black-box - a "hypercomputer" - cannot solve the "hyper-halting problem" for devices of its kind: i.e. given an hypercomputer program $H$ and an input $x$, an hypercomputer cannot decide if $H$ halts on $x$.

You can continue adding more black-boxes but the halting-problem will always be with you :-) (see Wikipedia for references about the Arithmetic Hierarchy)

  • $\begingroup$ In short: for any at least Turing-complete class of devices, there is no such device that can decide the halting problem of this (i.e. its) class. $\endgroup$ – Raphael Oct 4 '12 at 10:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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