In computability theory, the halting problem can be stated as follows: "Given a description of an arbitrary computer program, decide whether the program finishes running or continues to run forever". This is equivalent to the problem of deciding, given a program and an input, whether the program will eventually halt when run with that input, or will 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, what 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.
Jack Copeland (2004) attributes the term halting problem to Martin Davis.
Read more about Halting Problem: Background, Importance and Consequences, Representation As A Set, Sketch of Proof, Common Pitfalls, Formalization, Relationship With Gödel's Incompleteness Theorem, Recognizing Partial Solutions, History
Famous quotes containing the words halting and/or problem:
“People seldom see the halting and painful steps by which the most insignificant success is achieved.”
—Anne Sullivan (1866–1936)
“Consciousness is what makes the mind-body problem really intractable.”
—Thomas Nagel (b. 1938)