Lecture 11 - The Halting Problem
(Skeleton for Fall 2026.)
A_TM Is Undecidable
TODO: the diagonal proof, run exactly as the rerun of Lecture 2: programs as rows, inputs as columns, the machine D that flips the diagonal, contradiction on D applied to itself.
The Halting Problem
TODO: HALT_TM undecidable via reduction from A_TM; this is the first reduction of the course, do it slowly.
A Recognizable but Undecidable Language
TODO: A_TM is recognizable; the complement of A_TM is not recognizable; the picture of the world this gives us.
What Undecidability Means in Practice
TODO: no perfect halting checker, no perfect malware detector, no perfect optimizer; connect to Rice's theorem coming in Lecture 12.