The Halting Problem

I would have thought that every CS person would know about the halting problem. But they don’t!

The Halting Problem is a key result established by Turing. Intuitively, any universal model of computation (i.e., for every Turing-equivalent system) is such that it can express computations that we cannot determine (in finite resources) whether it will halt or not.

The proof is quite cool and similar to incompleteness proofs or diagonalization proofs (well, ok, it’s an instance thereof). Understanding this class of arguments 1) it just spectacularly cool; these are deep features of the world! and 2) very useful.

(I like Craig Kaplan’s discussion which is just one that came up early in a search. An interesting challenge would be to write up something that could be understood by a general audience. Hmm. Most of what I write on the Bits is motivational, i.e., I’m trying to convince you that it’s important, not explain the Bit per se. Even there, my inspiration for this one ran out: Why wouldn’t you want to know about about the Halting Problem?

Well, if anyone has an idea of what to do, let me know. But it’s better to post than not to post!)