Halting Problem

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 ...
Computability - Power of Automata - Power of Turing Machines - Beyond Recursively Enumerable Languages
... 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 ...
Recursion Theory - Areas of Research - Relative Computability and The Turing Degrees
... 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 ...
Recursive Languages And Sets - Undecidability - The 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 ...
The Undecidable Problem in Computability Theory
... 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.)