Module
Undecidability, the Halting Problem, and Reductions
Sign in to add this module to your path and practice.
About
Diagonalization proof that the halting problem (A_TM / HALT) is undecidable (and recognizable). Many-one (mapping) reductions. Proving further undecidable problems (emptiness of TM languages, equivalence, etc.) by reduction from HALT or A_TM. Introduction to RE vs. co-RE.
Goal
Prove HALT/A_TM undecidable by diagonalization; construct correct mapping reductions; use reductions to show new problems undecidable; classify languages as decidable, RE-but-not-decidable, or non-RE.
Unlocks
Tutor
Ask questions about this module.
Hi — I'm your tutor for Undecidability, the Halting Problem, and Reductions. Ask about the concepts, goal, or where you're stuck.