Monday, June 16, 2003

Do Not Halt, Do Not Collect $200

Some thoughts on the Halting Problem.

For the uninitiated, the Halting Problem is the classic instance of a problem that a Turing Machine cannot solve. It's simple enough: given a description of a Turing Machine and an input, will that Turing Machine's program ever finish? ("Halt" is what stops a Turing Machine's program, kind of like END in BASIC.)

The algorithm to solve it is pretty simple:
1. Wait until it stops. If it does, then yes, it will finish.
2. If it doesn't finish, wait until it doesn't finish. Then it won't.

The hole in the logic should be apparant. By a clever proof that I am a little bit too lazy to reproduce here, it can be proved that Turing Machines cannot solve this problem for all inputs. (The proof is based on the idea of feeding the Turing Machine to itself.)

The first response should be that this is stupid. Anyone can tell, for a vast array of programs, whether it will terminate or

int a = 7;
int b = 9;
int c = a+b;
return c;

Does that halt? Yes.

int a;
for(int i=0; i<10; i++) {
return a;

Does that halt? Yes.

In fact, for many reasonable programs, we can determine in polynomial time whether it will halt or not (remember, by the rules of the halting problem, we also get the input).

The question that interests me is not so much whether, in the worst case, I can construct a Byzantine case that will stump the will-it-Halt algorithm, but for what classes of input it will succeed, what classes it will fail, and, yes, what classes it is indeterminate. And, yes, I can determine that for many, but obviously not all, inputs.

An helpful policy here is to construct an algorithm for Will-it-Halt with three legal outputs: Yes, No, and I don't know. The restrictions on the algorithm are that if it says Yes, then the input machine must definitely halt, and if the input is No, it must definitely not halt. However, it may return "I don't know" for cases that will, in fact, halt, or not.

You don't need to simulate a Turing Machine to realize it won't halt:

while(true) {
print("The spoon does not exist.");

All of you Turing fundamentalists can simulate that one, maybe that will stop you from complaining to me about my ignorance of computational complexity. The rest of us can move on.

The question shifts now not to analyzing algorithms, but analyzing input sets. Think of it as looking for vulnerabilities; there exists some attack that will crash my algorithm (or, more accurately, never crash my algorithm). The question is not whether I can prove it safe, because Godel and Turing are still right; I can't ever prove it safe because it isn't safe, and I can't detect the unsafe cases because my detector in turn is vulnerable. (Does anyone else remember that cool part of Godel, Escher, Bach with the exploding record players?) But I can begin to make generalizations about the stability of certain algorithms to certain inputs.

Having established all that, tomorrow I'll argue that the Halting Problem is irrelevant.