Halting problem: Difference between revisions
imported>Alexander Wiebel m (umlaut) |
imported>Christopher J. Reiss No edit summary |
||
| Line 5: | Line 5: | ||
A revolution in mathematical thought was already underway due to Gödel'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. Limits were found to the power of sytematic computation. | A revolution in mathematical thought was already underway due to Gödel'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. Limits were found to the power of sytematic computation. | ||
The Halting Problem seeks to determine, for any given program P, | |||
: Will P terminate (halt) or continue indefinitely ? | : Will P terminate (halt) or continue indefinitely ? | ||
The solution was sought in a general sense for all programs P, that is, can we write a 'halting detector' program H, which will read any program P and determine if P terminates. | The solution was sought in a general sense for all programs P, that is, can we write a 'halting detector' program H, which will read any program P and determine if P terminates. | ||
Revision as of 14:01, 9 March 2008
The Halting Problem poses the question, "Is a computer program always predictable?" The surprising answer of "No." was given in 1936 in the form of the Church-Turing Thesis. This theorem proved that 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 one of the earliest undecidability results.
A revolution in mathematical thought was already underway due to Gödel'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. Limits were found to the power of sytematic computation.
The Halting Problem seeks to determine, for any given program P,
- Will P terminate (halt) or continue indefinitely ?
The solution was sought in a general sense for all programs P, that is, can we write a 'halting detector' program H, which will read any program P and determine if P terminates.
Intuitively one might be tempted to suggest, execute P and see what happens. The problem with this is we can never be certain that we've waited long enough for P to terminate. So the halting-detector H must be guaranteed to terminate in a finite period of time.
Were H to exist (which it doesn't), it would be a valuable tool indeed. To know that a program halts is equivalent to knowing that it was successful. For example, suppose we seek a counter-example to Goldbach's conjecture that every even number is the sum of two primes. We write a program Pg that ascends the even numbers, testing every possible sum for dual primality. Were we to possess the halting-detector H, we ask if Pg ever terminates (by calculating H(Pg)) and dispose of Goldbach's Conjecture.
Many programs are naturally written to continue running until they find a certain condition. In any case, a program can always be rewritten so that, upon 'success' the program stops, where upon failure it performs an infinite loop and 'hangs'. Thus, the Halting Problem really seeks to know, will P be successful?