title: "Lecture 12 - Reductions and Rice's Theorem"
unit: 2
lecture: 12

Lecture 12 - Reductions and Rice's Theorem

(Skeleton for Fall 2026.)

Reductions

TODO: mapping reducibility defined precisely (another drill definition); the logic of using reductions to prove undecidability, and the direction students always get backwards.

A Portfolio of Undecidable Problems

TODO: emptiness, equivalence, and regularity for Turing machines, each via reduction; a template students can reuse on problem sets.

Rice's Theorem

TODO: every nontrivial semantic property of the language of a TM is undecidable; proof; what "semantic" and "nontrivial" rule in and out; when you may cite Rice on a problem set versus when I want the reduction.