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.
This article is provided by FOLDOC - Free Online Dictionary of Computing (foldoc.org)
References in periodicals archive ?
The halting problem implies that some interesting problems are
known as the halting problem. (163) Turing, often considered "the
This paper provides us an easier way to understand the undecidability of the halting problem of Turing machines.
We prove the undecidability of this problem by reduction from the halting problem of reversible two-counter machines, which is proved undecidable in Morita (1996).
Chapters five and six consider the tasks computers "can and cannot perform." He explains Turing's Halting Problem and interestingly how limits in computing strikingly affect other types of inquiry.
Examples include the liar paradox, Zeno's paradoxes, the travelling salesman problem, Turing's halting problem, Godel's incompleteness theorem, and Schrodinger's cat.
There is even a discussion of the halting problem as studied by Alan Turning and the book maintains a focus on efficiency, often using the ?big O?
In 1936, Turing published a paper about the Turing machine (TM), the Universal Turing Machine (UTM), and the halting problem. He was interested in the undecidability of formal systems, as was his professor, David Hilbert.
Alan Turing, the father of computer science, used Godelian self-reference to prove the halting problem: It is not possible to write a computer program that can examine any arbitrary computer program to see whether the program will eventually stop or run forever.
After the concepts and theories are introduced, the equivalence of computable partial function and recursive partial function are demonstrated, in part through proofs of the unsolvability of the halting problem and of the enumeration theorem.
We use the halting problem of Turing machines on empty input as our undecidable problem.