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.
References in periodicals archive ?
This paper provides us an easier way to understand the undecidability of the halting problem of Turing machines.
Afterward, the halting problem has been discussed in general and at the last, the halting problem of Turing machines and its undecidability has been explained in a formal.
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).
Proof: We prove it by reduction from the halting problem with empty counters of 2-RCM.
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 ?
In 1936, Turing published a paper about the Turing machine (TM), the Universal Turing Machine (UTM), and the halting problem.
11) Turing proved the halting problem by assuming that a halting program existed and by submitting the augmented halting program for analysis to another copy of the halting program.
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.