robdickerson.net

As often happens, I spent some time today checking out what was new on http://programming.reddit.com. At the top of the list was this blog post: http://programmingkungfuqi.blogspot.com/2007/02/real-reason-why-building-software-is.html

I found it to be a pretty amusing post, and I think it was worth the read. But, near the end, the author says this:

Unfortunately for software developers, this place actually exists for us. The Halting Problem shows that we can never be certain of any result about any computation. It may run properly, it may become an endless loop, or it may give the completely wrong result. Adding concurrency adds on even more uncertainty into the situation. And we can PROVE this logically.

Well, I guess I should let you know that I have a little pet peeve about people incorrectly invoking halting problem undecidability to make a point. I’m new to blogging, but my understanding is that ranting about pet peeves is what it’s is all about, so get ready.

But, before I launch into my little rant, let me say that I am not an expert in the field of formal languages and computability theory. Maybe I fall into the “computability theory enthusiast” category, if such a thing exists. Anyway, the things I’m about to say are, to the best of my knowledge, correct, but please don’t get the impression I’m sitting over here with a Ph.D. in automata theory. (Although perhaps someday I shall posses that coveted degree).

So anyway, here are the two major fallacies I often hear people fall into when they discuss the halting problem. (Oh, and Wikipedia has a nice article on the halting problem if you’d like to read up on it). And a terminology note: when I say “computer,” I mean it in the modern, digital, Von Neuman, plastic and silicon way, and not the more ethereal “anything that does computations” way. So, here we go.

Incorrect Claim #1. Computers Are Turing Machines. Turing machines are a model for all computation, so all computers are Turing machines, right? Well, not quite. Turing machines have an infinite amount of memory. No modern computer (to the best of my knowledge) does. (A better model for an actual computer is a linearly bounded automaton).

For a given computer, there are things that a Turing machine can do that the computer cannot. (For example, any computation with a result that takes more memory to express than the computer has; an infinite amount of numbers, plus the pigeon hole principle, plus the computer’s finite memory guarantees such a result exists). The point I’m going for here is that, from the perspective of computational ability, Turing machine > computer.

And, when someone says “Computers are Turing machines,” it is often followed up with something like, “and so the halting problem says we can’t decide what programs will finish on a computer.” In other words, people tend to think that computer == Turing machine -> undecidability of halting problem on computers.

Well, technically, the halting problem is decidable for any program that can be run on a deterministic machine with finite memory (like a computer). Since such a machine has a finite (albeit huge) number of possible states, you can decide whether or not a program will halt by:

1. Start it running
2. Remember each state the machine has been in
3. If you see the same state twice, reject
4. If the machine halts, accept

Since the number of states is finite, 3 or 4 is guaranteed to happen (again, by the pigeon hole principle).

Of course, actually implementing a halting decider for a real computer is wildly impractical. The author of the aforementioned post (as well as anyone who makes similar claims) is likely trying to say that, for all practical purposes, you cannot decide the halting problem on a computer. Which is quite true — just remember the “for all practical purposes” part.

Incorrect Claim #2. Halting Behavior is Undecidable For Every Program. Again, not true. I often hear people making this claim, as the author of the post under discussion does: “The Halting Problem shows that we can never be certain of any result about any computation.” (Emphasis mine). Frankly, this is false. (Well, maybe you could wiggle out of this by having a debate on the semantics of “certain of,” but let’s not.)

There are, in fact, many programs for which the halting problem is decidable. Consider the trivial example of a program that, on any input, immediately halts. The result of that computation is a halt for every possible input. Or, consider the equally trivial example of a program that, on any input, immediately goes from one state to another and back again, in an infinite loop. That computation will never halt for any input, and the algorithm described above will correctly decide the machine as non-halting.

In fact, you can even make a recognizer for the class of problems that halt. (A “recognizer” is a program that returns “true” for any input in the class it is recognizing, and either returns “false” or fails to halt on any program not in that class. This is in contrast to a “decider,” which is not allowed to infinitely loop on “false” cases). The above algorithm, for example, is such a recognizer. It makes sense when you think about it; any program that terminates can be recognized as halting on the input it was given, since it, well… halted when given that input.

So, there are plenty of programs that can be determined to halt on given inputs. What the actual ‘undecidability of the halting problem’ result says is that a decider for the halting problem cannot be constructed that works on any arbitrary machine. You can make partial “deciders” that work for some machines, and even recognizers for all machines that halt, but never a decider that decides halting for all machines. Again, a little nit-picky, but if you’re going to talk all math-like, you’ve gotta play by the rules. Watch your existential quantifiers.

Back to the post I originally quoted — there are a couple of other things about the paragraph that bother me a little (I’m not sure how getting a “wrong” result relates to the halting problem, and I’m not sure what the author is claiming can be “proved logically”), but like I said, I think most people understand the point that is being made.

And I mean no disrespect for the author; the posting was a fun read, and I enjoyed his analogy. I just wish there was a little more attention to detail when a theoretical bomb like the Halting Problem is dropped into a discussion.

Please be careful.