Halting problem
The Halting problem is a problem in computer science. The problem is looking at a computer program and finding out if the program is going to run forever or not. We say that a program "solves the halting problem" if it can look at any other program and tell if that other program will run forever or not.
For example, a program like this:
while True: continue;
will loop forever, but the program
while False: continue;
stops very quickly.
Is there a program that solves the halting problem? It turns out there is not. We prove this fact by showing that if there is a program that solves the halting problem then something impossible happens. So for the moment we will act like there really is a program that solves the halting problem. Here, P is a function which will evaluate function F (called with argument I) and return true if it runs forever and false otherwise.
def P(F, I):
if F(I) runs forever:
return True;
else:
return False;
P can look at any program and find out if it will run forever or not. We use P to make a new program that we will call Q. What Q does is to look at another program and then answer the following question: "If we run this program and make it look at a copy of itself, will it run forever?". We can make Q because we have P. All we need to do is to tell Q to create a new program that is the old program looking at itself, and then use P to find out if the new program runs forever or not.
def Q(F): return P(F, F);
Now we make another program R. R looks at another program and asks Q for its answer on that program. If Q answers "yes, if we run this program and make it look at a copy of itself it will run forever", then R stops. If Q answers "no, if we run this program and make it look at a copy of itself, it will not run forever", then R enters an infinite loop and runs forever.
def R(F):
if Q(F):
return; //terminate
else:
while True: continue; //loop forever
Now we look at what happens if we make R look at a copy of itself. Two things can happen: it will either stop or run forever.
| run R(R) => calls Q(R) => calls P(R,R) => calls R(R) => leads to infinite loop ! => never halts by design |
|---|
If running R and making it look at a copy of itself does not run forever, then Q answered "yes, if we run this program and make it look at a copy of itself it will run forever". But Q said this when looking at R itself. So what Q actually said is: "yes, if we run R and make it look at a copy of itself it will run forever". So: If R running on a copy of itself does not run forever, then it does run forever. This is impossible.
If running R and making it look at a copy of itself runs forever, then Q answered "no, if we run this program and make it look at a copy of itself it will not run forever". But Q said this when looking at R itself. So what Q actually said is: "no, if we run R and make it look at a copy of itself it will not run forever". So: If R running on a copy of itself runs forever, then it does not run forever. This is also impossible.
No matter what happens, we get an impossible situation. We did something wrong, and we need to find out what it was. Most of the things we did were not wrong. We can not say "making a program look at a copy of itself is wrong", or "looking at what another program said and then going into a loop if it said one thing, and stopping if it said another thing" is wrong. It does not make sense to say that we are not allowed to do those things. The only thing that we did that looks like it could be wrong is that we pretended that a program like P exists in the first place. And since this is the only thing that could be wrong, and something must be wrong, this is it. This is the proof that a program like P does not exist. There is no program that solves the halting problem.
This proof was found by Alan Turing in 1936.
References
[change | change source]On computable numbers, with an application to the Entscheidungsproblem (PDF). 2. Proceedings of the London Mathematical Society. 1936. pp. 230–265. Archived from the original (PDF) on 2011-02-22. Retrieved 2008-07-27. This is the paper where Turing defines Turing machines, formulates the halting problem, and shows that it (as well as the Entscheidungsproblem) is unsolvable.