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 whether the program finishes running or will run forever.
Alan Turing proved in 1936 that a general algorithm 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.
Read more about this topic: Undecidable Problem
Famous quotes containing the words problem and/or theory:
“You are a problem and rune,
you are mystery;
writ on a stone.”
—Hilda Doolittle (1886–1961)
“Thus the theory of description matters most.
It is the theory of the word for those
For whom the word is the making of the world,
The buzzing world and lisping firmament.”
—Wallace Stevens (1879–1955)