Course contentsShow
← Computer Science
Lesson 1885 of 2,87242. Turing Machines and ComputabilityFree lesson

Reductions from the Halting Problem

Use the halting problem to prove other problems undecidable through reduction techniques.

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:

  1. Assume you have a decider for problem B
  2. Show how to use it to build a decider for the halting problem
  3. Contradiction: Since the halting problem is undecidable, your assumption must be wrong
  4. 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.