Difference between revisions of "Halting problem"
From Wiki @ Karl Jones dot com
Karl Jones (Talk | contribs) (First) |
Karl Jones (Talk | contribs) |
||
| Line 1: | Line 1: | ||
In [[computability theory]], the '''halting problem''' is the problem of determining, from a description of an arbitrary [[computer program]] and an input, whether the program will finish running or continue to run forever. | In [[computability theory]], the '''halting problem''' is the problem of determining, from a description of an arbitrary [[computer program]] and an input, whether the program will finish running or continue to run forever. | ||
| + | |||
| + | (TO DO: expand, illustrate, cross-reference.) | ||
| + | |||
| + | == Description == | ||
[[Alan Turing]] proved in 1936 that a general [[algorithm]] to solve the halting problem for all possible program-input pairs cannot exist. | [[Alan Turing]] proved in 1936 that a general [[algorithm]] to solve the halting problem for all possible program-input pairs cannot exist. | ||
| Line 14: | Line 18: | ||
* [[Alan Turing]] | * [[Alan Turing]] | ||
* [[Computability theory]] | * [[Computability theory]] | ||
| + | * [[Decision problem]] | ||
* [[Impossible Programs]] | * [[Impossible Programs]] | ||
* [[Paradox]] | * [[Paradox]] | ||
Revision as of 03:56, 9 September 2015
In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running or continue to run forever.
(TO DO: expand, illustrate, cross-reference.)
Description
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, which 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.
See also
External links
- Halting problem @ Wikipedia
