Neural Sync Active

Reductions — Proving Undecidability

Registry Synced

Reductions — Proving Undecidability

1939 words

10 min read

Reading compass

Now · 🎯 Learning Objectives

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

A reduction is like converting a problem you want to solve into one you already know how to solve. If you know how to decide whether a number is even, you can decide whether a number is odd by checking if (n+1) is even. Similarly, if we know the Halting problem is undecidable, we can prove other problems are undecidable by showing: "If I could decide problem X, I could decide the Halting problem — which is impossible."

1.2 Mapping Reduction

A \leq_m B

means: There exists a computable function

f

such that

w \in A \iff f(w) \in B

. (Diagram) Properties:

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

A_{TM} = \{\langle M, w \rangle \mid M \text{ is a TM and } M \text{ accepts } w\}

Theorem:

A_{TM}

is undecidable. Proof (diagonalization): Assume

H

decides

A_{TM}

. Construct

D

$D$ $D$ = "On input $\langle M \rangle$ $⟨ M ⟩$ :
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}$

HALT_{TM} = \{\langle M, w \rangle \mid M \text{ halts on } w\}

Reduction from $A_{TM}$ :

f(\langle M, w \rangle) = \langle M', w \rangle

where:

$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}$

E_{TM} = \{\langle M \rangle \mid L(M) = \emptyset\}

Reduction from $A_{TM}$ :

f(\langle M, w \rangle) = \langle M'\rangle

where:

$M'$ $M^{'}$ = "On input $x$ $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}$

REG_{TM} = \{\langle M \rangle \mid L(M) \text{ is regular}\}

Reduction from $A_{TM}$ : Transform

\langle M, w \rangle

into

\langle M' \rangle

where:

$M'$ $M^{'}$ = "On input $x$ $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

Theorem: Any non-trivial property of Turing machine languages is undecidable. A property

P

of languages is:

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

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

5. Common Pitfalls

Pitfall 1: Reversing the Reduction Direction

The mistake: Reducing

B

A_{TM}

to prove

B

is undecidable. Why students make it: The logic "this problem is hard" suggests it must reduce to something. How to catch it: To prove

B

undecidable, reduce a KNOWN undecidable problem (

A_{TM}

) TO

B

. If

B

were decidable,

A_{TM}

would be decidable. Correct approach:

A_{TM} \leq_m B

to prove

B

undecidable.

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

The mistake: Using Rice's theorem to prove properties about the machine itself (number of states, running time) are undecidable. Why students make it: Rice's theorem sounds like "everything about TMs is undecidable." How to catch it: Rice's theorem applies only to SEMANTIC properties — properties of the language

L(M)

, not of the machine

M

itself. Correct approach: Does the property depend only on

L(M)

? If it depends on how

M

works (state count, time complexity), Rice's theorem doesn't apply.

Pitfall 3: Forgetting to Show Both Directions

The mistake: Only showing one direction of the reduction. Why students make it: It's easier to reason about one direction. How to catch it: A reduction requires

w \in A \iff f(w) \in B

. Both directions must hold for the reduction to be valid. Correct approach: Prove both directions: If

w \in A

then

f(w) \in B

, AND if

f(w) \in B

then

w \in A

6. Key Concepts Reference

Concept	Definition	Application
Mapping reduction	$f$ computable, $w \in A \iff f(w) \in B$	Proving undecidability
$A_{TM}$	$\{ \langle M, w \rangle \mid M$ accepts $w \}$	Prototypical undecidable problem
$HALT_{TM}$	$\{ \langle M, w \rangle \mid M$ halts on $w \}$	Undecidable via $A_{TM}$ reduction
Rice's theorem	Non-trivial semantic properties undecidable	Quick undecidability proofs
$\leq_m$	Reduction direction	$A \leq_m B$ means $A$ reduces to $B$
TM-recognizable	Some TM halts-accepts on strings in $L$	Also called semi-decidable
Co-TM-recognizable	Complement is TM-recognizable	$\overline{L}$ is recognizable

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$ :

If $x \neq w$ , reject

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)

Let $P$ be non-trivial property of TM languages

Assume $\emptyset$ does NOT satisfy $P$ (if it does, work with $\overline{P}$ )

Let $B$ be a language that DOES satisfy $P$ (exists because P is non-trivial)

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$

If $M$ accepts $w$ : $L(M') = B$ → $\langle M' \rangle$ has property $P$

If $M$ doesn't accept $w$ : $L(M') = \emptyset$ → $\langle M' \rangle$ doesn't have property $P$

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