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

### Other articles related to "halting problem, problems, halting, problem":

**Halting Problem**- History

... of algorithms 1900 David Hilbert poses his "23 questions" (now known as Hilbert's

**problems**) at the Second International Congress of Mathematicians in Paris. 108) 1920–1921 Emil Post explores the

**halting problem**for tag systems, regarding it as a candidate for unsolvability ... (Absolutely unsolvable

**problems**and relatively undecidable propositions – account of an anticipation, in Davis, 1965, pp ...

... The

**halting problem**is easy to solve, however, if we allow that the Turing machine that decides it may run forever when given input which is a representation of ... The

**halting**language is therefore recursively enumerable ... of such a language is the complement of the

**halting**language that is the language consisting of all Turing machines paired with input strings where the Turing machines do not halt on their input ...

... many different sets that encode variants of the

**halting problem**, have two properties in common They are recursively enumerable, and Each can be translated into any other via a many-one reduction ... It can be shown that every recursively enumerable set is many-one reducible to the

**halting problem**, and thus the

**halting problem**is the most complicated recursively enumerable set with ... either computable or Turing equivalent to the

**halting problem**, that is, whether there is no recursively enumerable set with a Turing degree ...

**Halting Problem**

... In computability theory, the

**halting problem**is a decision

**problem**which can be stated as follows Given a description of a program and a finite input, decide whether the program eventually halts when ... Alan Turing proved in 1936 that a general algorithm to solve the

**halting problem**for all possible program-input pairs cannot exist the set of pairs (e,n) such that the program with description e halts on input n is ...

... In computability theory, the

**halting problem**is a decision

**problem**which can be stated as follows Given the description of an arbitrary program and a finite input, decide ... running on a Turing machine that solves the

**halting problem**for all possible program-input pairs necessarily cannot exist ... Hence, the

**halting problem**is undecidable for Turing machines ...

### Famous quotes containing the words problem and/or halting:

“War is not a life: it is a situation,

One which may neither be ignored nor accepted,

A *problem* to be met with ambush and stratagem,

Enveloped or scattered.”

—T.S. (Thomas Stearns)

“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.)