The Problem With The Halting Problem

Of course everybody knows the halting problem is undecidable, what is less known is why the halting problem is undecidable. Surprisingly, I think the problem comes from the fact that the proof is actually too simple. It's really only a few sentences and doesn't even involve any big words or anything. You don't have to follow along with a pencil and paper, recomputing each step of the proof to see how it was done. You just start reading and before you know it it's over. You read and understand every single word but feel like you've been gypped. Something about it just doesn't feel right. It's one of the most profound proofs in the theory of computation, but you don't feel any different after reading it. The problem is that the simplicity is deceptive. If you don't take the time to limber up your mind for all the bending it has to do, you'll skip right over it. So before we get into the proof, let's start with some mind-stretching.

The proof goes something like this:

1. Assume that the halting problem is decidable.
2. ???
3. Deduce that the universe doesn't exist.

Limber yet? Good.

Now we can address what you've been wondering this whole time; what the heck the halting problem is. The halting problem is just the problem of deciding whether a given program will eventually terminate or continue to run indefinitely on a given input. If it were decidable that would mean that for any given program on any given input, it would be theoretically possible to determine whether or not that program would halt on that input. Emphasis is of course on the fact that it would have to be decidable on any program and any input; solving trivial examples is obviously possible. Unfortunately the most obvious solution doesn't quite cut it. If you just run the program on the input and see if it halts, you would never know how long to let it run before deciding that it will never halt. The best you could do is wait a while and hope it halts, but if it didn't you still wouldn't know if it would eventually halt or not. Even with a time machine you could fast forward to the end of the universe and still never know if it really was going to loop forever or if it was just about to halt. If a solution exists it's going to involve a bit more cunning.

It may seem like it's really not even worth it to muster up the necessary cunning to solve the halting problem, but a solution would actually be incredibly valuable. Hard math problems like the Collatz conjecture would be trivially solvable; just make a program to do an exhaustive search of every number and give that program to the halting problem solver to see if it ever finishes. Done. There are a myriad of other undecidable problems that the halting-problem-solver would make short work of. Not to mention, how cool would it be to have a compiler that is able to warn you that the program you just compiled will never finish running. I know it would have saved me some debugging time.

Well, now that you're all excited about how awesome a solution to the halting problem would be, let's get to the reason it can never exist. Like we went over in the outline, step one of the proof is pretty simple, we just assume we have some program that can solve the halting problem. Let's call it Halting_Problem_Solver(p, i). Halting_Problem_Solver takes two parameters, the first is a program (p), and the second is some input (i). Halting_Problem_Solver returns true if the program p will ever halt on input i, and false if it will loop infinitely. Simple enough, right? Just make sure your mind is still limber for step two.

Now that we have a Halting_Problem_Solver, we're going to design a program which uses it to crash the universe. This is where it gets tricky. We'll call this second program Halting_Problem_Crasher(p). It takes one input, a program p. Halting_Problem_Crasher(p) is going to call Halting_Problem_Solver(p, p), which is to say it will see if program p will ever halt when given itself as input. Whatever Halting_Problem_Solver determines that p does with itself as its input, Halting_Problem_Crasher does the exact opposite. In other words, if it is determined that program p does eventually halt when given itself as input, Halting_Problem_Crasher enters an infinite loop. If it is determined that program p loops infinitely when given itself as input, Halting_Program_Crasher halts.

Here it is in some python-esque pseudo-code

Halting_Problem_Crasher(p):
  if(Halting_Problem_Solver(p, p) == Halts):
    while True: pass #infinte loop
  else:
    exit() #halt

Still with me? Ok, now what we're going to do is call Halting_Problem_Crasher(Halting_Problem_Crasher). That is, we're running Halting_Problem_Crasher with itself as input. Lets run through what happens. Halting_Problem_Crasher takes the program it's given and gives it to the Halting_Problem_Solver, using it as both of the parameters. So in this case, it calls
Halting_Problem_Solver(Halting_Problem_Crasher, Halting_Problem_Crasher)
So Halting_Problem_Solver is going to try to figure out if Halting_Problem_Crasher will loop infinitely or eventually halt with itself as input. But wait, that's what we were trying to figure out in the first place when we called
Halting_Problem_Crasher(Halting_Problem_Crasher)
So what should Halting_Problem_Solver determine? If it says it halts, Halting_Problem_Crasher loops. If it says it loops, Halting_Problem_Crasher halts. No matter what it says it's wrong. The only way it can work is by looping and halting simultaneously. The very existence of a solution to the halting problem proves that looping and halting are equivalent. And if looping and halting are equivalent, so are true and false, one and zero, up and down, etc. In other words, the existence of a solution to the halting problem would disprove the our very existence.