Rice's theorem: Worked examples — Coding deep dive

Before we shoot, one ultra-quick refresher of the words and symbols we will use in every example. Read them once, then never guess again.

Definition The vocabulary and symbols, spelled out on this page

$Σ$ (the alphabet) ::: the finite set of symbols an input string may be built from — think of it as the "keyboard" the machine reads, e.g. $Σ = {0, 1}$ . We always assume it is non-empty ( $∣Σ∣ \geq 1$ ), so at least one symbol exists. $Σ^{*}$ ::: the set of all finite strings you can type from $Σ$ (including the empty string). Because $∣Σ∣ \geq 1$ , there are strings of every length $0, 1, 2, \dots$ , so $Σ^{*}$ is an infinite set. $⟨ M ⟩$ (the encoding) ::: the machine $M$ written out as a finite string — its full instruction sheet (states, transitions) spelled as text so another machine can read it as input. "Feed $⟨ M ⟩$ to a decider" just means "hand the decider $M$ 's source code". r.e. (recursively enumerable) ::: a language $L$ is recursively enumerable — also called recognizable — if some Turing machine accepts every string in $L$ and never accepts any string outside $L$ (it may loop forever on those non-members). See Recursive vs Recursively Enumerable languages. Every $L (M)$ is r.e. by definition, because $M$ itself is such a machine. $L (M)$ ::: the language of $M$ — the exact set of input strings the machine $M$ accepts. $A_{T M}$ (the acceptance problem) ::: the language $A_{T M} = {⟨ M, w ⟩ : M accepts the input w}$ — the set of (code, input) pairs where the machine accepts that input. It is the classic undecidable language; see A_TM and undecidability. Note: accepts is stronger than halts — a machine can halt by rejecting. $P$ ::: the property we are testing, written as the set of r.e. languages that have it; and $L_{P} = {⟨ M ⟩ : L (M) \in P}$ is the set of machine codes whose language has the property. Semantic property ::: a yes/no question about $L (M)$ — the set of strings $M$ accepts — not about how the machine is wired. Non-trivial ::: there is at least one r.e. language that HAS the property, and at least one r.e. language that does NOT. (A "yes-witness" and a "no-witness", both of which must themselves be recognizable.) Undecidable ::: no Turing machine can answer the question correctly for every input and always halt.

Rice's theorem, compressed to a checklist we will run on each example:

Recall The reduction gadget from the parent (one-paragraph refresher — we cite it in Ex 1's verify)

Start from an acceptance question: "does $M$ accept the input $w$ ?", i.e. is $⟨ M, w ⟩ \in A_{T M}$ ? (This is acceptance, not mere halting — $M$ may halt by rejecting, and that counts as "does not accept".) The parent builds a gadget machine $G_{M, w}$ that on any input $x$ first simulates $M$ on $w$ ; if that simulation accepts, it then runs a fixed yes-witness machine $M_{P}$ on $x$ . Result: if $M$ accepts $w$ then $L (G_{M, w}) = L (M_{P}) \in P$ ; if not (reject or loop), $G_{M, w}$ never gets past step 1, so $L (G_{M, w}) = \emptyset \in / P$ . The gadget flips between a yes-language and a no-language exactly according to whether $⟨ M, w ⟩ \in A_{T M}$ — and that flip is only possible because both a yes-witness and a no-witness exist. ::: This is why non-triviality (two r.e. witnesses) is the whole engine.

The scenario matrix

Every question about "what does this program do?" falls into exactly one of these cells. The whole page is designed so each row gets its own worked example. (Recall $P$ = the property viewed as a set of r.e. languages, defined just above.)

#	Cell (the case class)	Semantic?	Non-trivial?	Verdict	Hits example
A	Plain semantic, both witnesses obvious	yes	yes	undecidable	Ex 1
B	Semantic but the "no" witness is the empty language	yes	yes	undecidable	Ex 2
C	The degenerate empty property $P = \emptyset$	yes	no (trivial)	decidable	Ex 3
D	The degenerate full property $P =$ all r.e.	yes	no (trivial)	decidable	Ex 4
E	Syntactic trap — looks semantic, is about the code	no	—	Rice silent → decidable	Ex 5
F	Real-world word problem (a linter / security check)	yes	yes	undecidable	Ex 6
G	Undecidable but still r.e. (limiting/finer case)	yes	yes	undecidable, & r.e.	Ex 7
H	Exam twist — property mentions the machine's steps but reduces to $L (M)$	subtle	yes	undecidable	Ex 8
I	Complement flip — $\emptyset \in P$ , so we flip	yes	yes	undecidable	Ex 9

Figure 1 — the map of cases. The big blue region is "semantic and non-trivial ⇒ undecidable". The two grey corners (C and D) are the only safe harbours where a decider exists — the trivial properties $P = \emptyset$ and $P =$ all r.e. The red band (E) is the syntactic trap where Rice is silent. Each yellow/green dot is one example below, planted in the region it lives in. Read the whole page as: "which coloured region does my question land in?"

The worked examples

Worked example Ex 1 — Cell A: "Does

$M$ accept the string hello?" Statement. $P = {L : hello \in L}$ . Decidable or not?

Forecast: guess YES or NO before reading. (Most people correctly smell "undecidable".)

Is it semantic? The condition " $hello \in L$ " talks only about the set $L$ , not about states/transitions. ✅ semantic. Why this step? Rice's first box. A property about wiring would knock us straight out of Rice.
Find a yes-witness. Take $L_{yes} = Σ^{*}$ (accept everything). It contains hello, so $L_{yes} \in P$ . ✅ Why this step? Non-triviality demands one r.e. language that has the property; $Σ^{*}$ is recognized by the always-accept machine, so it is r.e.
Find a no-witness. Take $L_{no} = \emptyset$ (accept nothing). It does not contain hello, so $L_{no} \in / P$ . ✅ Why this step? Non-triviality demands one r.e. language that lacks it; $\emptyset$ is recognized by the always-reject machine. Two r.e. witnesses found ⇒ non-trivial.
Apply Rice. Semantic ✅ + non-trivial ✅ ⇒ undecidable.

Verify: Both witnesses are genuinely r.e. (both are decidable, hence r.e.). Distinct membership of hello gives one YES, one NO. Plugging into the parent's gadget (refresher callout above): build $G_{M, w}$ using $M_{P} =$ the machine for $Σ^{*}$ ; then $⟨ M, w ⟩ \in A_{T M}$ (i.e. $M$ accepts $w$ ) $⟺ L (G_{M, w}) = Σ^{*} ∋ hello ⟺ ⟨ G_{M, w} ⟩ \in L_{P}$ . A decider for $L_{P}$ would therefore decide $A_{T M}$ — impossible. ✔

Worked example Ex 2 — Cell B: "Is

$L (M)$ infinite?" Statement. $P = {L : L is infinite}$ .

Forecast: guess. (Trap: "infinite feels like a size, not behaviour" — but size is a property of the set.)

Semantic? "Infinite" is a property of the set $L$ itself. ✅ Why this step? Cardinality of $L (M)$ cannot change if we only rewire the machine while keeping the accepted set fixed — so it depends only on $L (M)$ , passing Rice's first box.
Yes-witness. $L_{yes} = Σ^{*}$ is infinite (since $∣Σ∣ \geq 1$ there are strings of every length) and r.e. (always-accept machine). ✅ in $P$ . Why this step? Need an infinite recognizable language — easiest is "everything".
No-witness. $L_{no} = \emptyset$ is finite (size $0$ ) and r.e. (always-reject machine). ❌ not in $P$ . Why this step? The empty language is the universal r.e. "no" witness for any property the empty set lacks.
Apply Rice. ✅✅ ⇒ undecidable.
Recognizability (self-contained argument). Is $L_{P}$ even r.e.? No. Suppose a machine $E$ semi-decided " $L (M)$ is infinite", i.e. $E$ accepts $⟨ M ⟩$ whenever $L (M)$ is infinite. To justify accepting, any halting run of $E$ has read only finitely many facts about $M$ — it has witnessed at most finitely many accepted strings. But finitely many accepted strings are equally consistent with a finite language, so $E$ would also accept some $⟨ M^{'} ⟩$ with $L (M^{'})$ finite — a wrong answer. Contradiction, so no such $E$ exists: the property is not r.e. (And its complement " $L (M)$ is finite" is not r.e. either, so it is neither r.e. nor co-r.e.) Why this step? Undecidability is only the coarse verdict; the finer r.e./co-r.e. question separates Ex 2 (not r.e.) from Ex 7 (is r.e.). We argue it from scratch so this example stands alone.

Verify: $∣ Σ^{*} ∣ = \infty$ for $∣Σ∣ \geq 1$ , $∣ \emptyset ∣ = 0$ — the two r.e. witnesses differ, so $P$ is non-trivial. ✔

Worked example Ex 3 — Cell C (degenerate empty): "

$P = \emptyset$ — is $L_{P}$ decidable?" Statement. $P$ is the property that no r.e. language satisfies. What is the status of $L_{P} = {⟨ M ⟩ : L (M) \in P}$ ?

Forecast: Rice screams "undecidable" — but is Rice even allowed here?

Non-trivial? We need a yes-witness $L \in P$ . But $P = \emptyset$ means no language is in $P$ . So there is no yes-witness. ❌ Why this step? This is the whole point of the degenerate corner — one box of the checklist fails.
Rice silent. With no yes-witness, non-triviality fails, so Rice's hypothesis is not met. We may not conclude undecidable. Why this step? Rice is an implication; a false premise gives no information.
Decide it directly. $L (M) \in \emptyset$ is never true, so $L_{P} = \emptyset$ (the language of codes). The machine that always rejects decides it. Why this step? A constant answer is trivially computable.
Verdict: decidable (constant NO). Rice's excluded case, confirmed.

Verify: $L_{P} = {⟨ M ⟩ : L (M) \in \emptyset} = \emptyset$ , which is a recursive (decidable) language. ✔

Worked example Ex 4 — Cell D (degenerate full): "

$P =$ all r.e. languages." Statement. $P = {L : L is r.e.}$ — the property " $L (M)$ is recognizable", which every $L (M)$ trivially satisfies.

Forecast: decidable or undecidable?

Non-trivial? We need a no-witness $L \in / P$ . But every $L (M)$ is r.e. by definition, so no such $L$ exists. ❌ Why this step? The second half of non-triviality fails — the mirror image of Ex 3.
Rice silent, same reason as Ex 3. Why this step? No no-witness means the gadget cannot flip, so the reduction machinery has nothing to bite on.
Decide directly. Every machine code has the property, so $L_{P} = {all ⟨ M ⟩}$ . The machine that always accepts decides it. Why this step? Again a constant answer, trivially computable.
Verdict: decidable (constant YES).

Verify: $L_{P} =$ every valid $⟨ M ⟩$ , a decidable set (accept all well-formed encodings). ✔

Worked example Ex 5 — Cell E (syntactic trap): "Does

$M$ have exactly 5 states?" Statement. "Number of states of $M$ equals $5$ ." Is this a Rice property?

Forecast: the tempting answer is "property of $M$ ⇒ Rice ⇒ undecidable." Guess, then read.

Semantic? Ask: could two machines with the same language disagree on this answer? Yes — I can pad any machine with unreachable states, changing the count while $L (M)$ stays identical. ❌ not semantic. Why this step? This is the single most important test on the whole page. If the answer can change without $L (M)$ changing, it is syntactic.
Rice does not apply. Rice requires the property to depend only on $L (M)$ . It doesn't. Silent. Why this step? Applying Rice here is the classic exam death-trap.
Decide directly. Parse the description $⟨ M ⟩$ , count the states, compare to $5$ . This is a finite text operation. Why this step? Reading and counting symbols in a finite string always halts.
Verdict: decidable.

Verify (concept check): two machines $M_{1}$ (5 states) and $M_{2}$ ( $M_{1}$ + 1 unreachable state = 6 states) with $L (M_{1}) = L (M_{2})$ give different answers ⇒ property is not a function of $L (M)$ . ✔

Worked example Ex 6 — Cell F (real-world word problem): the security linter

Statement. A company wants a tool: "read any submitted program and warn if it ever prints a user's password to the log." Model "prints the password on some input" as accepting a certain string $p$ . Is a perfect such tool possible?

Forecast: they promise the linter is "always right and always finishes." Can they deliver?

Translate to a language property. "Program prints $p$ on some input" = $p \in L (M)$ where accept means "prints $p$ ". $P = {L : p \in L}$ . Why this step? Rice only speaks about language properties, so we must phrase the real request that way.
Semantic? Depends only on whether $p \in L (M)$ — about behaviour, not code layout. ✅ Why this step? Two implementations that print $p$ on the same inputs have the same $L (M)$ , so the answer tracks $L (M)$ only.
Non-trivial? Yes-witness $Σ^{*}$ (contains $p$ , r.e.); no-witness $\emptyset$ (lacks $p$ , r.e.). ✅✅ Why this step? Same two universal r.e. witnesses as Ex 1 — this is Ex 1 wearing a business suit.
Apply Rice. ⇒ undecidable. No perfect linter can exist. Real tools must be conservative (over-warn) — they trade correctness for termination.

Verify: $p \in Σ^{*}$ and $p \in / \emptyset$ for any string $p$ ⇒ non-trivial ⇒ undecidable, matching Ex 1's structure. ✔

Worked example Ex 7 — Cell G (undecidable

yet r.e.): " $L (M) \neq = \emptyset$ ?" Statement. $P = {L : L \neq = \emptyset}$ — "the machine accepts at least one string." Status?

Forecast: guess two things — (a) decidable? (b) even recognizable (r.e.)?

Semantic & non-trivial. About the set $L$ ✅. Yes-witness $Σ^{*} \neq = \emptyset$ (r.e.); no-witness $\emptyset$ (r.e.). ✅✅ ⇒ Rice ⇒ undecidable. Why this step? Standard checklist gives undecidability, both witnesses recognizable.
But is $L_{P}$ r.e.? Yes! Dovetail: simulate $M$ on all strings $w_{1}, w_{2}, \dots$ in parallel (a few steps each, round-robin). If any run accepts, halt and say YES. Why this step? Undecidable does not mean non-r.e. This example separates the two, hammering the parent's third "mistake" callout.
Why it can't also be co-r.e. (hence not decidable). If it were both r.e. and co-r.e., it would be decidable — but step 1 says it isn't. So it is r.e. but not co-r.e. Why this step? The r.e./co-r.e. sandwich theorem is what pins down the finer status.
Verdict: undecidable but recognizable — see Recursive vs Recursively Enumerable languages.

Verify: the dovetailer semi-decides " $\exists w : M accepts w$ "; non-triviality via $Σ^{*}$ vs $\emptyset$ confirms undecidability. ✔ (logical check below)

Figure 2 — undecidable does not mean unrecognizable. The outer blue box is all r.e. (recognizable) languages; the inner green box is the recursive (decidable) ones. The yellow star is the decision problem $L_{P} = {⟨ M ⟩ : L (M) \neq = \emptyset}$ from Ex 7: it sits inside the r.e. box but outside the green decidable box. The red arrow is the dovetailing semi-decider from step 2 — it can say YES when the answer is YES, which is exactly what "r.e." means, yet it can loop forever when the answer is NO, which is why it is not a decider. Contrast this with Ex 2's "infinite", which lands outside the whole blue box (not even r.e.).

Worked example Ex 8 — Cell H (exam twist): "Is there some input on which

$M$ halts?" Model of computation (state it first!). We fix $M$ to be a recognizer (an acceptor): on each input it may accept, reject (halt without accepting), or loop. Its language is $L (M) = {x : M accepts x}$ . Keeping recognizer-vs-decider straight is the whole trap here, because "halts" (accept or reject) is different from "accepts".

Statement. "Does $M$ accept at least one input?" (the language-flavoured reading). Trap or Rice?

Forecast: semantic or not?

Careful reading. Restricting to "does $M$ accept some input" is exactly $L (M) \neq = \emptyset$ — the property of Ex 7, which is a function of $L (M)$ . ✅ semantic. Why this step? Some "halting-flavoured" phrasings collapse onto a language property. You must check whether the wording pins down $L (M)$ (accepting) rather than mere halting.
Non-trivial. Same r.e. witnesses $Σ^{*}$ vs $\emptyset$ . ✅✅ Why this step? Both witnesses recognizable, so Rice's second box is satisfied.
Apply Rice ⇒ undecidable.
Contrast note (why the model matters). The raw "does $M$ halt (accept or reject) on some input" talks about both halting outcomes, not just the accepting set $L (M)$ , so it is not a pure Rice property; it is handled by a direct Halting Problem reduction instead. Same words, different model reading, different tool.

Verify: " $M$ accepts some input" $\equiv L (M) \neq = \emptyset$ , a non-trivial semantic property ⇒ undecidable (same r.e. witness pair as Ex 7). ✔

Worked example Ex 9 — Cell I (complement flip): "Is

$L (M) = \emptyset$ ?" done the flip way Statement. $P = {\emptyset}$ — "the machine accepts nothing." Here $\emptyset \in P$ , which is the case the parent's proof handles by flipping to $\overset{ˉ}{P}$ .

Forecast: does the " $\emptyset \in P$ " situation break Rice?

Semantic & non-trivial? Yes-witness $\emptyset \in P$ ; no-witness $Σ^{*} \in / P$ . Both are r.e. ( $\emptyset$ via the always-reject machine, $Σ^{*}$ via the always-accept machine), which is required before Rice may be invoked. Semantic ✅. So Rice already applies. Why this step? Non-triviality only needs one r.e. yes-witness and one r.e. no-witness — it does not care which side $\emptyset$ lands on, but it does insist both witnesses be recognizable.
The proof's flip. The parent's reduction assumed $\emptyset \in / P$ . Here it is in $P$ , so run the identical argument on the complement $\overset{ˉ}{P} = {L : L \neq = \emptyset}$ (Ex 7). Deciding $P$ would decide $\overset{ˉ}{P}$ (just negate the answer). Why this step? Undecidability is closed under complement, so proving $\overset{ˉ}{P}$ undecidable proves $P$ undecidable.
Verdict: undecidable — this is the classic $E_{T M}$ result via Mapping reductions.

Verify: $\emptyset \in P$ , $Σ^{*} \in / P$ , both r.e. ⇒ non-trivial; complement $\overset{ˉ}{P}$ is Ex 7's undecidable property, and undecidability transfers under complement. ✔

The one thing to walk away with

Recall Self-test

Which cell is "Is $L (M)$ a context-free language?" ::: Cell A/B — semantic, non-trivial (yes-witness $\emptyset$ , r.e.; no-witness any r.e. non-CFL such as ${a^{n} b^{n} c^{n}}$ ) ⇒ undecidable. Which cell is "Does $M$ 's start state have out-degree 3?" ::: Cell E — syntactic, Rice silent, decidable by inspection. Which cell is "Is $L (M)$ the set of all strings, i.e. $L (M) = Σ^{*}$ ?" ::: Cell A — semantic, non-trivial (yes-witness $Σ^{*}$ , r.e.; no-witness $\emptyset$ , r.e.) ⇒ undecidable.

Connections

Parent: Rice's theorem — the machine behind every verdict here.
A_TM and undecidability — the source of every reduction.
Halting Problem — Ex 8's contrast case.
Mapping reductions — the flip used in Ex 9.
Recursive vs Recursively Enumerable languages — the heart of Ex 7.
Rice-Shapiro theorem — refines Ex 7's "is it r.e.?" question.
Turing Machines — the model under all of it.