Reductions — Proving Undecidability

🎯 Learning Objectives

• Define mapping reductions and their properties
• Reduce the Halting problem to other problems
• Apply Rice's theorem to prove undecidability
• Distinguish between Turing-recognizable and co-recognizable
• Construct reduction functions

1. Introduction to Reductions

1.1 Intuition

1.2 Mapping Reduction

• If $B$ is decidable and $A \leq_m B$, then $A$ is decidable
• If $A$ is undecidable and $A \leq_m B$, then $B$ is undecidable
• If $A \leq_m B$ and $B \leq_m C$, then $A \leq_m C$ (transitive)

2. The Halting Problem

2.1 Definition

• $D$ = "On input $\langle M \rangle$:
  1. Run $H$ on $\langle M, \langle M \rangle \rangle$
  2. If $H$ accepts, reject; if $H$ rejects, accept" Then $D(\langle D \rangle)$ accepts iff $D$ does not accept $\langle D \rangle$ — contradiction.

3. Reduction Examples

3.1 Halting Problem $HALT_{TM}$

• $M'$ runs $M$ on $w$
• If $M$ accepts, $M'$ accepts
• If $M$ rejects, $M'$ loops forever Check: $\langle M, w \rangle \in A_{TM} \iff M$ accepts $w \iff M'$ halts on $w \iff \langle M', w \rangle \in HALT_{TM}$

3.2 Empty Language $E_{TM}$

• $M'$ = "On input $x$:
  1. If $x \neq w$, reject
  2. Run $M$ on $w$ and accept if $M$ accepts" Check: $\langle M, w \rangle \in A_{TM} \iff M$ accepts $w \iff L(M') = \{w\} \neq \emptyset \iff \langle M' \rangle \notin E_{TM}$ Wait — we need $f$ such that $w \in A_{TM} \iff f(w) \in E_{TM}$. Let me fix. $f(\langle M, w \rangle) = \langle M'\rangle$ where:
• $M'$ ignores input and runs $M$ on $w$
• If $M$ accepts, $M'$ accepts Then:
• If $M$ accepts $w$: $M'$ accepts all inputs → $L(M') = \Sigma^* \neq \emptyset$ → $\langle M' \rangle \notin E_{TM}$
• If $M$ does not accept $w$: $M'$ hangs or rejects → $L(M') = \emptyset$ → $\langle M' \rangle \in E_{TM}$ So $A_{TM} \leq_m \overline{E_{TM}}$, which means $E_{TM}$ is undecidable.

3.3 Regular Language $REG_{TM}$

• $M'$ = "On input $x$:
  1. If $x$ is of form $0^n1^n$, accept
  2. Run $M$ on $w$; if $M$ accepts, accept" Then:
• If $M$ accepts $w$: $L(M') = \Sigma^*$ (regular)
• If $M$ does not accept $w$: $L(M') = \{0^n1^n\}$ (not regular) Thus $A_{TM} \leq_m REG_{TM}$, so $REG_{TM}$ is undecidable.

4. Rice's Theorem

4.1 Statement

• Non-trivial: Some recognizable languages have it, some don't
• Semantic: Only depends on $L(M)$, not on $M$'s implementation Examples of undecidable properties:
• Is $L(M)$ empty?
• Is $L(M)$ regular?
• Is $L(M)$ finite?
• Does $L(M)$ contain the string $\varepsilon$?
• Is $L(M) = \Sigma^*$?

4.2 Proof Sketch

1. Let $P$ be a non-trivial property
2. Assume WLOG that $\emptyset$ does NOT have property $P$ (otherwise use $\overline{P}$)
3. Let $B$ be a language with property $P$ (exists because $P$ is non-trivial)
4. Reduce $A_{TM}$ to $P$: Transform $\langle M, w \rangle$ to $\langle M' \rangle$ where $M'$:
   • On input $x$, run $M$ on $w$; if $M$ accepts, run a TM that recognizes $B$ on $x$
5. If $M$ accepts $w$: $L(M') = B$ (has property $P$)
6. If $M$ doesn't accept $w$: $L(M') = \emptyset$ (does NOT have property $P$)
7. Deciding $P$ would decide $A_{TM}$ → impossible

5. Common Pitfalls

Pitfall 1: Reversing the Reduction Direction

Pitfall 2: Assuming Rice's Theorem Applies to Syntactic Properties

Pitfall 3: Forgetting to Show Both Directions

6. Key Concepts Reference

7. 📝 Practice Questions

Q1: Prove that $HALT_{TM}$ is undecidable by reduction from $A_{TM}$.

Answer:

Define reduction $f(\langle M, w \rangle) = \langle M', w \rangle$ where:

• $M'$ runs $M$ on $w$
• If $M$ accepts, $M'$ halts (accepts)
• If $M$ rejects, $M'$ enters infinite loop
• If $M$ loops (doesn't halt), $M'$ also loops

Then: $\langle M, w \rangle \in A_{TM}$ (M accepts w) ⇒ M halts on w ⇒ M' halts on w ⇒ $\langle M', w \rangle \in HALT_{TM}$. And $\langle M, w \rangle \notin A_{TM}$ (M doesn't accept w) ⇒ M either rejects or loops ⇒ M' loops ⇒ $\langle M', w \rangle \notin HALT_{TM}$.

Thus $A_{TM} \leq_m HALT_{TM}$, so $HALT_{TM}$ is undecidable. Q2: Use Rice's theorem to prove that $E_{TM}$ (empty language) is undecidable.

Answer:

$E_{TM} = \{\langle M \rangle \mid L(M) = \emptyset\}$. This is a semantic property of TM languages:

• It's non-trivial: some TMs accept $\emptyset$ (e.g., TM that immediately rejects), some don't (e.g., TM that accepts everything).
• It's semantic: it depends only on $L(M)$, not on $M$'s implementation.

By Rice's theorem, any non-trivial semantic property is undecidable. Therefore $E_{TM}$ is undecidable. Q3: Show that the complement of $A_{TM}$ (the set of $\langle M,w \rangle$ where $M$ does NOT accept $w$) is not Turing-recognizable.

Answer:

If $\overline{A_{TM}}$ were Turing-recognizable, then both $A_{TM}$ and $\overline{A_{TM}}$ would be recognizable, making $A_{TM}$ decidable. But $A_{TM}$ is undecidable. Therefore $\overline{A_{TM}}$ is not Turing-recognizable.

More formally: A language is decidable iff both it and its complement are Turing-recognizable. Since $A_{TM}$ is not decidable (it's undecidable), and $A_{TM}$ IS Turing-recognizable (the universal TM recognizes it), its complement $\overline{A_{TM}}$ must NOT be Turing-recognizable. Q4: Construct a reduction from $A_{TM}$ to $E_{TM}$.

Answer:

$f(\langle M, w \rangle) = \langle M' \rangle$ where $M'$:

• On input $x$:
  1. If $x \neq w$, reject
  2. Run $M$ on $w$; if $M$ accepts, accept

Then:

• If $M$ accepts $w$: $L(M') = \{w\} \neq \emptyset$ → $\langle M' \rangle \notin E_{TM}$
• If $M$ doesn't accept $w$: $L(M') = \emptyset$ → $\langle M' \rangle \in E_{TM}$

This shows $A_{TM} \leq_m \overline{E_{TM}}$. So $E_{TM}$ is undecidable (if it were decidable, so would $\overline{E_{TM}}$ and thus $A_{TM}$). Q5: Why doesn't Rice's theorem apply to the property "M has exactly 25 states"?

Answer: Because this is a syntactic property of the TM description, not a semantic property of the language $L(M)$. It depends on how the machine is constructed, not on which strings it accepts. Rice's theorem only applies to semantic properties of the LANGUAGE. The number of states is a property of the machine representation $\langle M \rangle$, not of $L(M)$. Q6: Prove Rice's theorem: Any non-trivial property of TM languages is undecidable.

Answer: (Sketch)

1. Let $P$ be non-trivial property of TM languages
2. Assume $\emptyset$ does NOT satisfy $P$ (if it does, work with $\overline{P}$)
3. Let $B$ be a language that DOES satisfy $P$ (exists because P is non-trivial)
4. Define reduction $f(\langle M, w \rangle) = \langle M' \rangle$:
   • $M'$ on input $x$: runs $M$ on $w$; if $M$ accepts, runs a recognizer for $B$ on $x$
5. If $M$ accepts $w$: $L(M') = B$ → $\langle M' \rangle$ has property $P$
6. If $M$ doesn't accept $w$: $L(M') = \emptyset$ → $\langle M' \rangle$ doesn't have property $P$
7. Thus $A_{TM} \leq_m P$, so $P$ is undecidable. Q7: Show that $A_{TM}$ is Turing-recognizable but not co-Turing-recognizable.

Answer:

$A_{TM}$ is Turing-recognizable: The universal TM $U$ recognizes $A_{TM}$. On input $\langle M, w \rangle$, $U$ simulates $M$ on $w$ and accepts if $M$ accepts. If $M$ loops, $U$ loops. So $U$ recognizes $A_{TM}$.

$A_{TM}$ is NOT co-Turing-recognizable: If $\overline{A_{TM}}$ were also recognizable, then $A_{TM}$ would be decidable (since both $A_{TM}$ and its complement are recognizable). But $A_{TM}$ is undecidable. Therefore $\overline{A_{TM}}$ is not recognizable. Q8: Define the language $EQ_{TM} = \{\langle M_1, M_2 \rangle \mid L(M_1) = L(M_2)\}$. Show it's undecidable.

Answer:

Reduce $E_{TM}$ to $EQ_{TM}$. Let $M_{reject}$ be a TM that rejects all inputs (L($M_{reject}$) = ∅). Define $f(\langle M \rangle) = \langle M, M_{reject} \rangle$.

Then: $\langle M \rangle \in E_{TM} \iff L(M) = \emptyset \iff L(M) = L(M_{reject}) \iff \langle M, M_{reject} \rangle \in EQ_{TM}$.

Since $E_{TM}$ is undecidable, $EQ_{TM}$ is undecidable. (Also follows from Rice's theorem: "does M₁ equal M₂?" is a non-trivial semantic property.)

8. 🔗 Cross-References

• Week 8 - Decidability: Undecidable problems
• Week 10 - Complexity: From undecidability to intractability
• BSCS4021 (Advanced Algorithms): NP-completeness reductions Join Discord PreviousDecidabilityNextComplexity