5
$\begingroup$

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?

$\endgroup$
6
  • 7
    $\begingroup$ Just in case, a problem does not solve a problem. $\endgroup$ Oct 3, 2012 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$ Oct 4, 2012 at 4:29
  • 2
    $\begingroup$ The Halting Problem is not a solution, as its name states its a problem. $\endgroup$
    – Jodrell
    Oct 4, 2012 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, 2012 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$ Oct 4, 2012 at 10:48

2 Answers 2

15
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

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)

$\endgroup$
1
  • $\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, 2012 at 10:05

Your Answer

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

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