Solving the halting problem

Any computer user knows that, form time to time, a piece of software gets stuck, "crashing" into an endless loop of calculations, and making the computer unable to perform any other tasks. If a human user notices the computer in such a state, she will usually try to abort the task, sometimes simply by restarting the computer. Because getting into infinite tasks can drastically curtail a computer's effectiveness, operating systems and program compilers will often have checks, looking for tell-tale signs that a program might get stuck. But by a well-known theorem no such checks are perfect.

The proof of this theorem is easy. Say a program H can look at any piece of software and decide, yes or no, whether that software will eventually halt. Software can occasionally take input; perhaps H should be a function of two variables, the string encoding the software S, and the string encoding the input T: H = H(S,T). We can modify this into a new function G(S) = H(S,S), with just a few extra lines telling H that whenever it wants to look at T, actually look at the single piece of input S — i.e. G asks whether S will halt when it acts on itself. Then apply an easy alteration to G, making it less useful: if the answer is yes, rather than saying so, just start counting numbers starting at 1 and going forever. Now apply G to itself, and while you're waiting, perhaps you should get a haircut from the Barber of Seville.

However, none of this takes into consideration the actual facts of real computers. A computer is not, however much we'd like to model it as such, an idealized Turing machine. Its (finite) memory and speed depends such variables as what brand it is, and when it was built.

It is this last observation — that computers are getting faster — that allows us a solution to the Halting Problem. Computers are not just getting faster; they're getting faster exponentially. For some constant C > 1, the number of calculations one of next year's computers can perform in a minute will be at least C times faster than the number of calculations one of this year's computers can perform in a minute.

Thus, rather than run a program we expect to take a long time (if it doesn't halt, it will probably take at least a year) on just one computer, let's set up a fancy server farm, and swap out old computers for new ones. Now, let's hope that Moore was wrong, and that computer speeds grow slightly faster than he predicted, for the following reason: next year's computer, being C times as fast, has 1/C the life-span, and a new C-times better computer is released not at the end of another year, but after just 1/C of a year.

So, this year, we perform some number of calculations N, on our computers. Next year, we get a C-times better computer, but only have it for 1/C as long, so perform another N calculations. Then we get a C^2 computer, and have it for 1/C^2 years. Etc. After infinitely many iterations of this, we've performed N+N+N+... = infinitely many calculations. But our total time spent? 1+1/C+1/C^2+... = C/(C-1) < infinity.

So our algorithm to solve the Halting Problem? Eventually, we will have computers that can totally automate their own server-farm swapping and growing and building (so we really will be able to swap out old for new parts arbitrarily fast). So let's program on of these to do that — to build itself at the predicted exponential rate. And while it's doing so, run whatever program we want to know about. If in less than C/(C-1) time the program stops, then we know it will stop and after how many calculations, and even what the outcome will be. And if it doesn't, then we get the other answer.