What exactly is the halting problem?
EDIT (much later than original answer): MarkCC of Good Math, Bad Math recently wrote up an excellent discussion of the Halting problem with concrete examples. The halting problem is basically a formal way of asking if you can tell whether or not an arbitrary program will eventually halt. In other words, can you write a … Read more