# halting problem

Also found in: Wikipedia.

## 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.

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.

Want to thank TFD for its existence? Tell a friend about us, add a link to this page, or visit the webmaster's page for free fun content.

Link to this page: