halting problem

1 definition found

halting problem - Free On-line Dictionary of Computing (26 May 2007) :

  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)