Reductions from the Halting Problem
You'll learn how to prove new problems undecidable by showing they're at least as hard as the halting problem.
The Core Technique
Now that you know the halting problem is undecidable, you have a powerful tool: reduction. A reduction transforms one problem into another. If you can show that solving problem B would let you solve the halting problem, then B must also be undecidable—otherwise you'd have solved the halting problem, which we proved impossible.
How Reductions Work
Think of it like this: Suppose you want to prove that "predicting tomorrow's weather perfectly" is impossible. If you can show that perfect weather prediction would let you solve the halting problem (perhaps by encoding programs as atmospheric conditions), then weather prediction must be impossible too.
The pattern:
- Assume you have a decider for problem B
- Show how to use it to build a decider for the halting problem
- Contradiction: Since the halting problem is undecidable, your assumption must be wrong
- Conclude: Problem B is undecidable
Classic Example Structure
Want to prove "Does Turing machine M accept any input?" is undecidable?
- Convert any halting problem instance (M, w) into this question
- If M halts on w, construct M' that accepts something
- If M doesn't halt on w, construct M' that accepts nothing
- Solving the emptiness question solves halting—contradiction!
This technique cascades: each undecidable problem becomes a stepping stone to prove others undecidable.
Key Takeaway: Reductions transform the halting problem into other problems, proving those problems undecidable by inheritance—if you could solve them, you'd magically solve the unsolvable halting problem.