Lesson 240
Computability & the Halting Problem
Decidable vs Undecidable · Diagonalization Proof
1:00Why some problems no algorithm can ever solve — and the rigorous proof, via a self-referential contradiction, that the Halting Problem is undecidable.
By the end, you can
- Define decidable, recognizable, and undecidable, and place the Halting Problem correctly in the hierarchy.
- Explain why simulating a program can confirm halting but never confirm looping.
- Trace through Turing's contradiction proof step by step, identifying the role of `trouble`.
- Explain why the proof defeats every algorithm, not just the specific one considered.
- Apply the counting argument to explain why most problems have no program.
- State Rice's Theorem and identify which questions about programs it makes undecidable.
- Distinguish "undecidable" (mathematically proved impossible) from "unsolved" (open research question).
Up next in Theory of Computation & Compilers
