Halting problem
Published:
The halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running or continue to run forever.
Alan Turing proved in 1936 that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist. A key part of the proof was a mathematical definition of a computer and program, which became known as a Turing machine; the halting problem is undecidable over Turing machines. It is one of the first examples of a decision problem.
See also
Artificial Intelligence, Computer Complexity, Turing Machines, Automata theory, Theory of computation
Papers
- Turing, Alan M. (1936-37). On Computable Numbers, With An Application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, Series 2 42: 230-265.
Books
- Sipser, Michael (2006). Introduction to the Theory of Computation (Second ed.). PWS Publishing. pp. 173-182. “Section 4.2: The Halting Problem”