Rice's theorem

Why it exists

After $A_{TM}$ and the halting problem one would like a quick way to see that a new question about Turing machines is undecidable, without a new reduction every time. Rice's theorem is that quick way for a large family of questions: anything non-trivial about the language a machine recognises is undecidable. GATE uses it in true/false questions about Turing machines ("is it decidable whether $L(M)$ is ...?").

Prerequisites

You need $A_{TM}$, its undecidability and mapping reductions (the halting problem).

Precise definitions

Let $\mathcal{P}$ be a property of recognisable languages, that is, a set of recognisable languages (for example "the empty language", "languages with at least two strings", "regular languages"). Define the decision problem

$L_{\mathcal{P}} = \{\langle M \rangle : M \text{ is a Turing machine and } L(M) \in \mathcal{P}\}.$

• $\mathcal{P}$ is trivial if it contains all recognisable languages or none of them. Otherwise it is non-trivial: at least one recognisable language has the property and at least one does not.
• The question about $\langle M \rangle$ is semantic when it depends only on the language $L(M)$: if $L(M_1) = L(M_2)$ then $M_1$ and $M_2$ answer alike. (This is what the definition of $L_{\mathcal{P}}$ expresses.)

Rice's theorem. If $\mathcal{P}$ is a non-trivial property of recognisable languages, then $L_{\mathcal{P}}$ is undecidable.

How it works

The proof

Assume first that the empty language does not have the property $\mathcal{P}$ (otherwise use the complementary property $\overline{\mathcal{P}}$, which is non-trivial too, and note that a decider for one gives a decider for the other). Since $\mathcal{P}$ is non-trivial, pick a machine $M_P$ with $L(M_P) \in \mathcal{P}$.

Reduce $A_{TM}$ to $L_{\mathcal{P}}$. Given $\langle M, w \rangle$ construct the machine $M_w$:

On input $x$: first run $M$ on $w$ (ignoring $x$). If $M$ accepts $w$, run $M_P$ on $x$ and accept if $M_P$ accepts. (If $M$ rejects or loops, $M_w$ rejects or loops.)

Then

$L(M_w) = \begin{cases} L(M_P) \in \mathcal{P} & \text{if } M \text{ accepts } w, \\ \emptyset \notin \mathcal{P} & \text{otherwise,} \end{cases}$

so $\langle M_w \rangle \in L_{\mathcal{P}} \iff \langle M, w \rangle \in A_{TM}$. The map $\langle M, w \rangle \mapsto \langle M_w \rangle$ is computable (it only writes down a machine). A decider for $L_{\mathcal{P}}$ would decide $A_{TM}$, which is impossible. $\qquad\blacksquare$

The table runs the construction for the simplest choice of $M_P$ (accept every string). For six real pairs $(M, w)$ it shows the behaviour of $M_w$ on four inputs $x$: either it accepts all of them (when $M$ accepts $w$) or none (when $M$ rejects or loops on $w$):

Using the theorem

To show that a question about $L(M)$ is undecidable: state the property as a set $\mathcal{P}$ of languages, check that it is a property of the language and that it is non-trivial (give one machine with the property and one without), and conclude.

What Rice's theorem does not cover

Properties of the machine, not of the language. "Has an even number of states", "has a transition that writes a blank", "halts within $k$ moves on $w$": these depend on the description of $M$ (or on a bounded part of its behaviour) and are decidable by inspecting or simulating the machine for a bounded time. Simulating for $k$ moves always terminates; the answer agreed with a second simulator for $k \le 11$ on all short inputs of six machines.

Behaviour that two machines with the same language may differ on. "Halts on the empty input" and "halts on every input" are not properties of the language, since a machine can accept the same strings while looping or halting elsewhere. Example: the decider for $a^n b^n$ and its halting variant (every halting rejection replaced by an endless loop) accept exactly the same language (checked on all strings up to length $8$), but the first halts on the input $a$ (rejecting) while the second never halts on it. So Rice's theorem does not apply to such questions; they are undecidable by direct reductions from the halting problem instead.

Trivial properties. "$L(M)$ is a recognisable language" holds for every machine; the question is decidable (the answer is always yes). The same for the property "$L(M)$ is not recognisable".

The language class matters. The theorem is about recognisable languages. For a different model, results change: all the properties above are decidable for DFAs ($E_{DFA}$, $EQ_{DFA}$, finiteness).

Worked examples

Cheat box

Traps and GATE patterns

Connections

Rice's theorem generalises the reduction used for $E_{TM}$ (halting problem); it uses the machine descriptions and the universal machine (TM variants); the contrast with decidable problems for automata is on the page on decidable languages.

PYQs

Which of the following is/are undecidable?

Which of the following languages are undecidable? Note
that <M> indicates encoding of the Turing machine M.
L1 = <M> | L(M) = φ}
L2 = {<M, w, q>| M on input w reaches state q in exactly
100 steps}
L3 = {<M>|L(M) is not recursive}
L4 = {<M>|L(M) contains at least 21 members}?

Consider the following problems. L(G) denotes the
language generated by a grammar G. L(M) denotes the
language
accepted
by
a
machine
M.
(I) For an unrestricted grammar G and a string w,
whether w∈L(G).
(II) Given a Turing machine M, whether L(M) is
regular.
(III)Given two grammar G1 and G2, whether L(G1) =
L(G2).
(IV) Given an NFA N, whether there is a deterministic
PDA P such that N and P accept the same language.
Which one of the following statement is correct?

Consider the following languages.
L1 = { ⟨M⟩ | M takes at least 2016 steps on some input },
L2 = { ⟨M⟩ | M takes at least 2016 steps on all inputs },
and
L3 = { ⟨M⟩ | M accepts ε },
Where for each Turing machine M, ⟨M⟩ denotes a specific
encoding of M.
Which one of the following is TRUE?

Let <M> be the encoding of a Turing machine as a
string over Σ = {0, 1} Let L = { <M> |M is a Turing
machine that accepts a string of length 2014}. Then, L
is :

Which of the following is/are undecidable?
1. G is a CFG. Is L(G) = φ?
2. G is a CFG. Is L(G) = Σ*?
3. M is a Turing machine. Is L(M) regular?
4. A is a DFA and N is an NFA. Is L(A) = L(N)?

Self-check

Revision card

References