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 ...)
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.
Wikipedia's extensive entry [Wikipedia] 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 24 August 2017.
HTML page formatted Tue Feb 12 10:57:42 2019.
Cite this as:
Paul E. Black, "halting problem", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 24 August 2017. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/haltingProblem.html