for class on Tuesday April 25, 2000
Please read Sections 10.7 and 10.8 of the Schneider and Gersting text, and be prepared to discuss the following:
The text contains an actual proof, disguised in friendly prose, of the famous and notorious Halting Problem. We will go through this proof very slowly. Your best preparation for this class would be to read Section 10.7 several times, and think hard about the final step. The development of Turing machine S is perhaps slightly unfriendly. Here is what is S does: it takes as its input a description of some Turing machine M--any Turing machine--and answers the question, "Does Turing machine M halt if it is given its own description as input?" Of course it conveys its answer in a peculiar way: if M halts, S doesn't halt, and vice-versa. Even posing this question may seem a little silly, since very few Turing machines would take Turing machine descriptions as legitimate input. But if you did give a Turing machine its own description on the tape, it will either eventually halt or it won't, and that's the only question we're asking.
The final mind-bending step is to have S look at a description of itself, which leads to a contradiction: S halts if S doesn't halt, and vice versa. This beautiful result, seemingly so peculiar and narrow, has profound implications for the study of computation.
Course evaluations will be done during the last part of this class.