halting problem

   The problem of determining in advance whether a particular
   program or algorithm will terminate or run forever.  The
   halting problem is the canonical example of a provably
   unsolvable problem.  Obviously any attempt to answer the
   question by actually executing the algorithm or simulating
   each step of its execution will only give an answer if the
   algorithm under consideration does terminate, otherwise the
   algorithm attempting to answer the question will itself run
   forever.

   Some special cases of the halting problem are partially
   solvable given sufficient resources.  For example, if it is
   possible to record the complete state of the execution of the
   algorithm at each step and the current state is ever identical
   to some previous state then the algorithm is in a loop.  This
   might require an arbitrary amount of storage however.
   Alternatively, if there are at most N possible different
   states then the algorithm can run for at most N steps without
   looping.

   A program analysis called termination analysis attempts to
   answer this question for limited kinds of input algorithm.

   (1994-10-20)