Halting problem: Difference between revisions
imported>Christopher J. Reiss No edit summary |
imported>J. Noel Chiappa m (Checklisting) |
||
| Line 1: | Line 1: | ||
{{subpages}} | |||
The Halting Problem was posed in the 1930's and asks, in simplest terms, "Is a computer always predictable?" It came as a surprise to many that the answer is "No." In 1936 the Church-Turing thesis 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 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, "Is a computer always predictable?" It came as a surprise to many that the answer is "No." In 1936 the Church-Turing thesis 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 established in the Church-Turing thesis of 1936 and gave rise to the modern field of study called Computability. | ||
Revision as of 22:11, 4 March 2008
The Halting Problem was posed in the 1930's and asks, in simplest terms, "Is a computer always predictable?" It came as a surprise to many that the answer is "No." In 1936 the Church-Turing thesis 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 established in the Church-Turing thesis of 1936 and gave rise to the modern field of study called Computability.
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. Limits were found to the power of sytematic computation.
More speficially, 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?