Rice’s theorem and the Post Correspondence Problem

1. To prove P undecidable, which direction of reduction?
   Stuck? Peek at 5.3 Reductions and proving undecidability

   • A ≤ₘ B: computable f, x ∈ A ⇔ f(x) ∈ B. A ≤ B ⇔ A̅ ≤ B̅. Transitive.
   • B dec ⇒ A dec; A undec ⇒ B undec; B RE ⇒ A RE; A not RE ⇒ B not RE.
   • Prove P hard: A_TM ≤ P. E_TM co-RE not RE; NE_TM RE; EQ_TM, TOTAL, FINITE neither.

   Read lesson 5.3

2. Is the complement of A_TM RE?
   Stuck? Peek at 5.2 The diagonal language and the halting problem

   • L_d = {wᵢ : wᵢ ∉ L(Mᵢ)}: not RE (co-RE).
   • A_TM = {⟨M,w⟩ : M accepts w}: RE, not recursive; complement not RE.
   • HALT_TM: RE, undecidable; complement not RE.
   • REC = RE ∩ co-RE.

   Read lesson 5.2

3. Decider vs recognizer?
   Stuck? Peek at 4.3.1 Recursive vs recursively enumerable; deciders and recognizers

   • Recognizer: accepts L, may loop outside. RE = recognizable = semi-decidable = enumerable.
   • Decider: halts always. Recursive = decidable.
   • REC ⊆ RE. Enumerator ⇔ recognizer (dovetailing). Shortlex enumeration ⇔ recursive.

   Read lesson 4.3.1

A code-review bot that checks “does this program ever print ‘hello’?”, “does it accept any palindrome?”, “is its output the same as the reference solution?”. Rice’s theorem says every such bot must fail on some program — any question about what a program’s language is, as opposed to how the program is written, is undecidable unless the answer is the same for all programs.

“Does M have more than 10 states?” and “Is L(M) finite?” — which one does Rice’s theorem cover?

Prediction check

Only “Is L(M) finite?” — a property of the language. “More than 10 states” is a property of the machine’s code: just count, so it is decidable. Rice says nothing about it.

Rice’s theorem

“Property of the language” means: if L(M₁) = L(M₂) then both or neither have it. Proof idea: assume ∅ lacks P (else use the complement); pick M_P with L(M_P) ∈ P; reduce A_TM by building M′ that first runs M on w and, if accepted, behaves like M_P. L(M′) has P ⇔ M accepts w.

When Rice does not apply

• Trivial properties: “L(M) is RE” (always true) — decidable (answer yes).
• Machine properties: “M has 5 states”, “M halts on ε within 100 steps”, “M ever writes a 1 within 10 steps on input 0” — decidable by inspection or bounded simulation.
• “M halts on ε” is about M’s behaviour, not L(M) — Rice doesn’t apply directly, but it is undecidable anyway (reduction from HALT).

RE or not? (Rice–Shapiro, short form)

Rice says undecidable; it does not say whether the property is RE. Rule of thumb: “L(M) contains some particular string / is non-empty” is RE (guess and check); “L(M) is empty / finite / = Σ* / regular” is not RE. A property of RE languages can only be RE if it is closed upward and witnessed by a finite set of strings.

Post Correspondence Problem (PCP)

PCP is undecidable (alphabet with ≥ 2 symbols); it is RE (try all sequences). For a one-letter alphabet it is decidable. PCP is the usual tool for proving grammar questions undecidable: ambiguity of CFGs, emptiness of the intersection of two CFLs, universality of CFGs.

Putting it together

• Rice: any non-trivial question about what a TM accepts is undecidable.
• Questions about the code or bounded runs are decidable.
• PCP is undecidable and powers grammar undecidability results.

Rice checklist
 1. Property of L(M)? (same language ⇒ same answer)       no → Rice silent
 2. Non-trivial over RE languages?                         no → trivially decidable
 3. Yes and yes → undecidable.  RE? only if "witnessed by finitely many strings" (≠ ∅, contains w)

Undecidability is now in your hands. The last lesson collects every answer into one master table: which questions are decidable for regular, DCFL, CFL, CSL, recursive and RE languages — the most reused fact sheet in GATE TOC.

1. MSQ

   Which are undecidable by Rice’s theorem?

   1. L(M) is finite
   2. L(M) contains 101
   3. M has exactly 3 states
   4. L(M) is regular
2. MCQ

   { ⟨M⟩ : L(M) ≠ ∅ } is:

   1. decidable
   2. RE but undecidable
   3. co-RE but not RE
   4. neither
3. MCQ

   PCP is undecidable for alphabets of size:

   1. 1
   2. ≥ 2
   3. only 3
   4. none
4. MCQ

   Rice’s theorem does NOT apply to:

   1. L(M) is empty
   2. L(M) = Σ*
   3. M halts within 20 steps on ε
   4. L(M) is a CFL

• Rice’s theorem
• non-trivial property
• property of the language vs of the machine
• Post Correspondence Problem (PCP)

1. Rice’s theorem?
   Reveal answer

   Every non-trivial property of the language of a TM is undecidable.
2. Does Rice apply to “M has 5 states”?
   Reveal answer

   No — that is about the machine; decidable.
3. Is PCP decidable?
   Reveal answer

   No (|Σ| ≥ 2); unary PCP is decidable.
4. Is {⟨M⟩ : L(M) ≠ ∅} RE?
   Reveal answer

   Yes (but undecidable).