Difference between revisions of "Halting problem"
From Wiki @ Karl Jones dot com
Karl Jones (Talk | contribs) |
Karl Jones (Talk | contribs) (→See also) |
||
| (One intermediate revision by the same user not shown) | |||
| Line 15: | Line 15: | ||
* [[Algorithm]] | * [[Algorithm]] | ||
* [[Alan Turing]] | * [[Alan Turing]] | ||
| + | * [[Busy beaver]] | ||
* [[Computability theory]] | * [[Computability theory]] | ||
* [[Decision problem]] | * [[Decision problem]] | ||
| + | * [[Generic-case complexity]] | ||
| + | * [[Geoffrey K. Pullum]] | ||
| + | * [[Gödel's incompleteness theorem]] | ||
* [[Impossible Programs]] | * [[Impossible Programs]] | ||
| + | * [[Kolmogorov complexity]] | ||
| + | * [[Machine that always halts]] | ||
| + | * [[P versus NP problem]] | ||
* [[Paradox]] | * [[Paradox]] | ||
| + | * [[Termination analysis]] | ||
| + | * [[Worst-case execution time]] | ||
== External links == | == External links == | ||
Latest revision as of 06:52, 20 September 2016
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.
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
- Algorithm
- Alan Turing
- Busy beaver
- Computability theory
- Decision problem
- Generic-case complexity
- Geoffrey K. Pullum
- Gödel's incompleteness theorem
- Impossible Programs
- Kolmogorov complexity
- Machine that always halts
- P versus NP problem
- Paradox
- Termination analysis
- Worst-case execution time
External links
- Halting problem @ Wikipedia
