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:
“One thing in any case is certain: man is neither the oldest nor the most constant problem that has been posed for human knowledge.”
—Michel Foucault (1926–1984)
“No theory is good unless it permits, not rest, but the greatest work. No theory is good except on condition that one use it to go on beyond.”
—André Gide (1869–1951)