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 provablyunsolvable 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)