Halting problem: Difference between revisions
imported>Christopher J. Reiss No edit summary |
imported>Christopher J. Reiss mNo edit summary |
||
| Line 13: | Line 13: | ||
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. | 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 | Many programs are naturally written to continue running until something is found, or a certain condition is attained. Other programs can always be trivially modified to behave this way. Any well defined question about the eventual behavior of a program can be restated in terms of Halting. Thus the Halting Problem is really question about a programs long-term behavior in general. | ||
Revision as of 13:06, 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 something is found, or a certain condition is attained. Other programs can always be trivially modified to behave this way. Any well defined question about the eventual behavior of a program can be restated in terms of Halting. Thus the Halting Problem is really question about a programs long-term behavior in general.