# halting problem

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,^{1} 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.