Halting problem: Difference between revisions
imported>Christopher J. Reiss (New article, related to new Lambda Calculus article) |
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 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. This result was established in the Church-Turing thesis of 1936 and gave rise to the modern field of study called Computability. | 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 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 have predictable behavior, however, there will always exist other programs whose behavior cannot be predicted. 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 14:45, 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 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 have predictable behavior, however, there will always exist other programs whose behavior cannot be predicted. This result was established in the Church-Turing thesis of 1936 and gave rise to the modern field of study called Computability.