Halting problem

From Wiki @ Karl Jones dot com
Jump to: navigation, search

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

External links