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)
“If we parents accept that problems are an essential part of life’s challenges, rather than reacting to every problem as if something has gone wrong with universe that’s supposed to be perfect, we can demonstrate serenity and confidence in problem solving for our kids....By telling them that we know they have a problem and we know they can solve it, we can pass on a realistic attitude as well as empower our children with self-confidence and a sense of their own worth.”
—Barbara Coloroso (20th century)