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:
“Of the two
who feign anger,
sulk in mock sleep,
and give ear
to the other’s halting sighs,
who’s the winner?”
—Hla Stavhana (c. 50 A.D.)
“We have heard all of our lives how, after the Civil War was over, the South went back to straighten itself out and make a living again. It was for many years a voiceless part of the government. The balance of power moved away from it—to the north and the east. The problems of the north and the east became the big problem of the country and nobody paid much attention to the economic unbalance the South had left as its only choice.”
—Lyndon Baines Johnson (1908–1973)