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)
Nearby terms:
HALMAT « Hal/S « Halt and Catch Fire « halting
problem
» Hamilton » Hamiltonian cycle » Hamiltonian path
|
