Rice's Theorem
Every nontrivial property of a machine's language is undecidable.
The idea
Theorem (Rice's Theorem).
Let $P$ be a nontrivial property of the language a Turing machine recognizes. Then no algorithm decides, given a machine description $\langle M \rangle$, whether $L(M)$ has property $P$.
Each hypothesis restricts the theorem's reach. A property of the language depends on the set $L(M)$ and on nothing else, so $L(M_1) = L(M_2)$ forces the same verdict for $M_1$ and $M_2$. Properties like the machine has seven states or the machine halts within fifty steps fail this test: they concern the description or the run, and two machines recognizing the same language can differ on both. Nontrivial means some machine's language has the property and some machine's language lacks it. $L(M)$ is Turing-recognizable holds for every machine, so it is trivial — and decidable, by always answering yes.
The theorem settles infinitely many questions at once. Is $L(M)$ empty? Finite? Regular? Does it contain a particular string? Each is a nontrivial property of the language, so each is undecidable, with no separate argument required. The figure shows the shape of a reduction: a computable map $f$ carries every string $w$ inside a problem $A$ to a string $f(w)$ inside $B$, and every $w'$ outside $A$ to an $f(w')$ outside $B$, so $w \in A$ if and only if $f(w) \in B$ — and a decider for $B$ would therefore decide $A$.
Two cautions. The theorem constrains semantic properties only; syntactic conditions and resource-use conditions lie outside its scope and may well be decidable. And undecidable concerns algorithms that must work for all machines — for a particular machine, we may still settle the property by inspection.
Ways to work on it
- Walkthrough. Semantic vs. syntactic, trivial vs. nontrivial, and the reduction from the acceptance problem.
- Practice. Decide whether Rice's Theorem proves a given problem undecidable.
- Hardest. Choose the witness machine in a reduction and rule out non-semantic properties.
Not sure where to start? Take the ten-question placement test.