Halting problem: Difference between revisions
imported>Christopher J. Reiss No edit summary |
imported>Christopher J. Reiss No edit summary |
||
| Line 1: | Line 1: | ||
The Halting Problem was posed in the 1930's and asks, in simplest terms, "Can we always predict what a computer will do?" A revolution in mathematical thought was already underway due to Godel's Incompleteness Theorem of 1931, which demonstrated that certain theorems in mathematics, although true, cannot be proven. In other words, limits had been discovered to the power of formal, axiomatic reasoning. The Halting Problem can be viewed as a variant of this result in the field of Computation. Suprisingly to many, limits were found to the power of computation : No systematic method exists, or can ever exist, which predicts the behavior of all computer programs. Specific programs may be predictable, | The Halting Problem was posed in the 1930's and asks, in simplest terms, "Can we always predict what a computer will do?" A revolution in mathematical thought was already underway due to Godel's Incompleteness Theorem of 1931, which demonstrated that certain theorems in mathematics, although true, cannot be proven. In other words, limits had been discovered to the power of formal, axiomatic reasoning. The Halting Problem can be viewed as a variant of this result in the field of Computation. Suprisingly to many, limits were found to the power of computation : No systematic method exists, or can ever exist, which predicts the behavior of all computer programs. Specific programs may be predictable, but there will always exist other programs whose behavior is unknown. This result was established in the Church-Turing thesis of 1936 and gave rise to the modern field of study called Computability. | ||
Revision as of 13:48, 24 February 2008
The Halting Problem was posed in the 1930's and asks, in simplest terms, "Can we always predict what a computer will do?" A revolution in mathematical thought was already underway due to Godel's Incompleteness Theorem of 1931, which demonstrated that certain theorems in mathematics, although true, cannot be proven. In other words, limits had been discovered to the power of formal, axiomatic reasoning. The Halting Problem can be viewed as a variant of this result in the field of Computation. Suprisingly to many, limits were found to the power of computation : No systematic method exists, or can ever exist, which predicts the behavior of all computer programs. Specific programs may be predictable, but there will always exist other programs whose behavior is unknown. This result was established in the Church-Turing thesis of 1936 and gave rise to the modern field of study called Computability.