Rice's theorem

WHY does this theorem even exist?

WHAT is "behavior" vs "structure"?

• Behavioral (semantic) property = a property of the language $L(M)$ — the set of strings the machine accepts. Example: "does $M$ accept the empty string?", "is $L(M)$ infinite?", "is $L(M)=\emptyset$?".
• Structural (syntactic) property = a property of the machine description itself, not of what it computes. Example: "does $M$ have 7 states?", "does $M$ ever write a blank?". These are often decidable and Rice says nothing about them.

The Statement

The two excluded trivial cases (which are decidable):

• $P = \varnothing$ (no language has it) → always answer "no".
• $P = \text{all r.e. languages}$ → always answer "yes".

DERIVATION from first principles (reduction from Halting / $A_{TM}$)

Setup. Let $P$ be non-trivial. We use the undecidable language $A_{TM} = \{\langle M,w\rangle : M \text{ accepts } w\}$.

Step 1 — Pick a baseline. WLOG assume $\varnothing \notin P$ (the empty language does not have the property). Why this step? If $\varnothing \in P$ instead, just prove undecidability for the complement property $\bar P$; deciding $P$ would decide $\bar P$, so it's symmetric. So we lose nothing.

Step 2 — Grab a witness. Since $P$ is non-trivial and $\varnothing\notin P$, there exists some language $L(M_P) \in P$ with a machine $M_P$ recognizing it. Why this step? Non-triviality guarantees at least one "yes" example. We need a target language that does have the property to switch into.

Step 3 — The gadget. Given input $\langle M,w\rangle$, build a new machine $G_{M,w}$ that on input $x$ does:

1. Ignore $x$ for now. First run $M$ on $w$ (simulate).
2. If $M$ accepts $w$, then run $M_P$ on $x$ and accept iff $M_P$ accepts $x$.

Why this step? This is the heart. Trace the two worlds:

• If $M$ accepts $w$: step 1 finishes, so $G_{M,w}$ behaves exactly like $M_P$, hence $L(G_{M,w}) = L(M_P) \in P$.
• If $M$ does not accept $w$: step 1 never finishes, $G_{M,w}$ never reaches step 2, accepts nothing, so $L(G_{M,w}) = \varnothing \notin P$.

So: $L(G_{M,w}) \in P \iff M \text{ accepts } w.$

Step 4 — Contradiction. Suppose a decider $R$ for $L_P$ exists. Feed it $\langle G_{M,w}\rangle$: $R$ says "yes" $\iff L(G_{M,w})\in P \iff M$ accepts $w$. That decides $A_{TM}$ — impossible. Therefore $L_P$ is undecidable. $\blacksquare$

Worked Examples

Common Mistakes (Steel-manned)

Connections

• Halting Problem — the seed; Rice generalizes it.
• A_TM and undecidability — the language we reduce from.
• Mapping reductions — the proof technique (build a gadget machine).
• Recursive vs Recursively Enumerable languages — undecidable ≠ non-r.e.
• Rice-Shapiro theorem — refines Rice to decide recognizability.
• Turing Machines — the underlying model.

Flashcards

Concept Map

Hinglish (regional understanding)