Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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?
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)
