The halting problem is: Given a program and inputs for it, decide whether it will run forever or will eventually stop. This is not the same thing as actually running a given program and seeing what happens. The halting problem asks whether there is any general prescription for deciding how long to run an arbitrary program so that its halting or non-halting will be revealed.

 

In a celebrated 1936 paper,¹ Alan Turing proved that the halting problem is undecidable: there's no way to construct an algorithm that is always able to determine whether another algorithm halts or not. From this it follows that there can't be an algorithm that decides whether a given statement about natural numbers is true or not. The undecidability of the halting problem provides an alternative proof of Gödel's incompleteness theorem. This is because if there were a complete and consistent axiomatization of all true statements about natural numbers, then we would be able to create a set of rules that decides whether such a statement is true or not. Another amazing consequence of the undecidability of the halting problem is Rice's theorem, which states that the truth of any non-trivial statement about the function that is defined by an algorithm is undecidable. So, for example, the decision problem "will this algorithm halt for the empty string" is already undecidable. Note that this theorem holds for the function defined by the algorithm and not the algorithm itself. It is, for example, quite possible to decide if an algorithm will halt within 100 steps, but this isn't a statement about the function that is defined by the algorithm. Many problems can be shown to be undecidable by reducing them to the halting problem. However, Gregory Chaitin has given an undecidable problem in algorithmic information theory that doesn't depend on the halting problem.

 

While Turing's proof shows that there can be no general method or algorithm to determine whether algorithms halt, individual instances of that problem may very well be susceptible to attack. Given a specific algorithm, one can often show that it must halt, and in fact computer scientists often do just that as part of a correctness proof. But every such proof requires new arguments: there is no mechanical, general way to determine whether algorithms halt. And there's another caveat. The undecidability of the halting problem relies on the fact that computers are assumed to have a memory of potentially infinite size. If the memory and external storage of a machine is limited, as it is for any real computer, then the halting problem for programs running on that machine can be solved with a general algorithm (albeit an extremely inefficient one).

 

Reference

1. Turing, A. M. "On Computable Numbers, with an Application to the Entscheidungsproblem." Proc. London Math. Soc. Ser. 2, 42: 230–265, 1937.