Exercises — Rice's theorem

Test each: if I rewrite the machine into a totally different-looking machine that accepts the exact same strings, does the answer change?

• (a) Semantic. "Accepts hello" depends only on the set of accepted strings.
• (b) Syntactic. Two machines accepting the same language can have 5 vs 500 states — the answer changes though $L(M)$ did not.
• (c) Semantic. Finiteness is a fact about the set $L(M)$.
• (d) Syntactic. "Start state is accepting" is about the wiring diagram. (Note: it does imply $M$ accepts the empty string — but you can also accept the empty string without the start state being accepting, so the two are not the same property.)

Answers: (a) semantic, (b) syntactic, (c) semantic, (d) syntactic.

$P$ is non-trivial iff there is a YES-language and a NO-language among r.e. languages. But every language $L(M)$ that a Turing machine recognizes is r.e. by definition. So every language in our universe has $P_1$ — there is no NO-language. $P_1$ is trivial (always "yes"), hence decidable — a decider just prints YES. Rice does not apply.

False. State-count is syntactic. You literally read the description $⟨M⟩$ and count states → decidable. Rice only speaks about non-trivial semantic properties.

Property $P=\{{\Sigma }^{\ast }\}$ — the single language of all strings.

• Semantic? Yes — it only mentions $L(M)$. ✅
• Non-trivial? Need a YES and a NO language.
  • YES witness: $M_{\text{yes}}$ = "accept every input immediately", so $L(M_{\text{yes}})={\Sigma }^{\ast }\in P$.
  • NO witness: $M_{\text{no}}$ = "reject every input", so $L(M_{\text{no}})=\varnothing \notin P$. Both r.e. → non-trivial. ✅

By Rice: undecidable. $■$

$P=\{L:L\text{ contains some string of even length}\}$.

• Semantic? Yes — about which strings are in $L(M)$. ✅
• YES witness: $L=\{\epsilon \}$ (the empty string $\epsilon$ has length $0$, which is even) — this is r.e. and lies in $P$.
• NO witness: $L=\varnothing$ contains no strings at all, so no even-length string → $\notin P$. r.e. ✅ Non-trivial → undecidable by Rice. $■$

$P=\{L:L\text{ is finite}\}$.

• Semantic ✅.
• YES witness: $L=\varnothing$ is finite ($0$ elements) → in $P$.
• NO witness: $L={\Sigma }^{\ast }$ is infinite → not in $P$. Non-trivial → undecidable. $■$

Careful — halting is a property of $M$'s running, not purely of $L(M)$. Two machines can accept the same language $L$ yet differ in halting: one loops forever on rejected inputs, another cleanly rejects them. So "halts on every input" is not determined by $L(M)$ alone → it is not a semantic property in Rice's sense, and Rice's theorem as stated does not apply.

(It happens to be undecidable anyway, but you must prove that by a direct reduction from the Halting Problem — see Halting Problem — not by citing Rice.) Verdict: Rice does NOT directly apply; property is not semantic.

$P=\{L:L\ne \varnothing \}$.

• Semantic ✅.
• NO witness: $\varnothing$ itself is not in $P$ (it equals the empty set). So here $\varnothing \notin P$ — the baseline the parent's Step 1 assumes.
• YES witness: ${\Sigma }^{\ast }\ne \varnothing$ → in $P$. Non-trivial → undecidable.

Baseline note: because $\varnothing \notin P$, the gadget $G_{M,w}$ from the parent proof works directly: when $M$ loops on $w$, $G_{M,w}$ accepts nothing → language $\varnothing \notin P$; when $M$ accepts $w$, $G_{M,w}$ mimics a YES-witness → language in $P$. No complement swap needed. $■$

Does $\varnothing$ have the property "contains $\epsilon$"? The empty language contains nothing, so $\epsilon \notin \varnothing$ → $\varnothing \notin P$. Good — baseline holds, no complement trick.

• YES witness: $L=\{\epsilon \}$ (or ${\Sigma }^{\ast }$) contains $\epsilon$ → in $P$.
• NO witness: $\varnothing$ → not in $P$. Non-trivial → undecidable. $■$

First fix the baseline. Is $\varnothing$ regular? Yes ($\varnothing$ is a regular language). So $\varnothing \in P$ here — we must work with the complement property $\bar{P}=\{L:L\text{ is NOT regular}\}$, for which $\varnothing \notin \bar{P}$. Deciding $P$ ⇔ deciding $\bar{P}$, so it suffices to show $\bar{P}$ undecidable.

Pick a YES-witness for $\bar{P}$: the non-regular r.e. language $A=\{0^n{1}^n:n\ge 0\}$, recognized by some machine $M_A$.

Gadget. On input $x$, machine $G_{M,w}$ does:

1. Run $M$ on $w$ (ignore $x$ for now).
2. If $M$ accepts $w$, run $M_A$ on $x$; accept iff $M_A$ accepts $x$.

Two worlds:

• $M$ accepts $w$ ⇒ step 1 finishes ⇒ $G_{M,w}$ behaves as $M_A$ ⇒ $L(G_{M,w})=A$, which is not regular ⇒ $\in \bar{P}$.
• $M$ does not accept $w$ ⇒ step 1 never finishes ⇒ $G_{M,w}$ accepts nothing ⇒ $L(G_{M,w})=\varnothing$, which is regular ⇒ $\notin \bar{P}$.

Hence $L(G_{M,w})\in \bar{P}⟺M$ accepts $w$. A decider for $\bar{P}$ would decide $A_{TM}$ — impossible. So $\bar{P}$, and therefore $P$, is undecidable. $■$

• Semantic ✅.
• YES witness: $L=\{a,b,c\}$ (any three fixed distinct strings) — finite, r.e., in $P$.
• NO witness: $\varnothing$ (size $0\ne 3$) — in fact $\varnothing \notin P$, giving a clean baseline. Non-trivial → undecidable by Rice.

(Note $\varnothing \notin P$ so no complement trick needed; the gadget mimics a machine for $\{a,b,c\}$ when $M$ accepts $w$, and accepts $\varnothing$ otherwise.) $■$

• Semantic ✅ (both conjuncts are about $L(M)$).
• YES witness: $L=\{0\}$ — regular and non-empty → in $P$.
• NO witness: $\varnothing$ — regular but empty, fails the "non-empty" clause → $\notin P$. Both r.e., non-trivial → undecidable. (Baseline: $\varnothing \notin P$, clean.) $■$

• Undecidable but r.e.: $P=\{L:L\ne \varnothing \}$, i.e. $L_P=\{⟨M⟩:L(M)\ne \varnothing \}$. It's undecidable (L3.2). It is r.e.: dovetail-simulate $M$ on all strings in parallel; the moment any run accepts, halt and accept. If $L(M)\ne \varnothing$ you eventually see an acceptance; if empty, you loop — exactly an r.e. recognizer.
• Not even r.e.: the complementary property $P^{\prime }=\{L:L=\varnothing \}$, i.e. $L_{P^{\prime }}=\{⟨M⟩:L(M)=\varnothing \}$. If it were r.e., then together with $L_P$ being r.e. we'd have both $L_{P^{\prime }}$ and its complement r.e. ⇒ $L_{P^{\prime }}$ decidable — contradicting Rice. So $L_{P^{\prime }}$ is not r.e.

Punchline: Rice guarantees undecidable, but says nothing about r.e.-ness — that is a finer, separate question, sometimes settled by Rice-Shapiro theorem. $■$

• "$L(M)$ is r.e." — as we saw in L1.2 this is the trivial property (all our languages are r.e.). Trivial ⇒ decidable (print YES). Rice explicitly excludes trivial properties, consistent.
• "$L(M)$ is co-r.e." — the class of languages that are r.e. and co-r.e. is exactly the recursive (decidable) languages. "$L(M)$ is recursive" is a non-trivial semantic property (e.g. $\varnothing$ recursive ∈ P; $A_{TM}$ r.e.-but-not-recursive ∉ P), so by Rice it's undecidable. Rice hands you undecidability; determining whether $L_P$ is itself r.e. needs Rice–Shapiro or a direct argument. Answers: "is r.e." → trivial, decidable. "is recursive" → non-trivial, undecidable.

The property references the number of states, a fact about $⟨M⟩$ that two same-language machines can disagree on. Therefore it is not a function of $L(M)$ → not semantic → Rice does not apply. The single deciding test (top of the page's flowchart): "Do all machines with the same language give the same answer?" Here the answer is no, so the property is syntactic. It is in fact decidable by counting states. $■$

Semantic + non-trivial ⇒ undecidable ::: This is the whole Rice checklist — verify both before invoking it. What makes a property trivial? ::: It holds for every r.e. language or for none — no YES/NO pair of witnesses. Does Rice say anything about r.e.-ness of $L_P$? ::: No — only undecidability; use Rice–Shapiro or reductions for that.