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:
“Congress seems drugged and inert most of the time. ...Its idea of meeting a problem is to hold hearings or, in extreme cases, to appoint a commission.”
—Shirley Chisholm (b. 1924)
“If my theory of relativity is proven correct, Germany will claim me as a German and France will declare that I am a citizen of the world. Should my theory prove untrue, France will say that I am a German and Germany will declare that I am a Jew.”
—Albert Einstein (1879–1955)