(classic problem)
Definition: Is there an algorithm to determine whether any arbitrary program halts? Turing proved the answer is, no. Since many questions can be recast to this problem, we can conclude that some programs are absolutely impossible, although heuristic or partial solutions are possible.
Generalization (I am a kind of ...)
undecidable problem.
See also uncomputable problem, Turing machine.
Note: In more detail, can there be a program that, when given any arbitrary program, finishes in finite time and correctly answers "Yes, the program you gave me halts for all inputs" or "No, the program you gave me does not halt for some inputs."
This is an informal wording of what Turing proved. Please do not refer to this page if you claim to refute his proof.
Author: PEB
Wikipedia's extensive entry including related problems and a link to Turing's original paper. Eric W. Weisstein's entry for Halting Problem.
Alan Turing, On computable numbers, with an application to the Entscheidungsproblem, Proceedings of the London Mathematical Society, Series 2, vol 42 (1936-37) pages 230-265.
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 17 December 2004.
HTML page formatted Mon Feb 2 13:10:39 2015.
Cite this as:
Paul E. Black, "halting problem", in
Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 17 December 2004. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/haltingProblem.html