Rice's Theorem

"The only way to parse Perl 5 is to run it or to simulate it using a language of equivalent power... There is no guarantee a Perl 5 program will ever finish running and no guarantee it will ever finish parsing itself... In this article I will use Rice's Theorem to prove that Perl is unparseable." - Jeffrey Kegler

For many examples where the language is a set of Turing Machines (code), there is a very easy shortcut to show the language is not decidable. But to explain that shortcut, known as Rice's Theorem, we need to define some more terminology.

Definition

A property of a Turing Machine is said to be functional if it depends only on the language of the Turing Machine, and not on the details of the implementation (states and transitions).

That is, the property is functional if whenever two machines accept the same language either both machines have the property or neither does.

Example

• Whether a TM accepts 00011 (i.e., whether 00011 is in the language) is a functional property
• Whether the TM accepts at least ten strings (i.e., whether its language has at least 10 elements) is a functional property.
• Whether the TM has at least 3 states is not a functional property.
• Whether the TM rejects 00011 is not a functional property. \ "The TM that rejects every input" and "the TM that infinite-loops on every input" have the same language (the empty set), but only one of these TMs rejects 00011.

Definition

A property of Turing Machines is said to be nontrivial if there's at least one TM with the property and at least one TM lacking the property.

It is trivial if all TMs have the property or TMs lack the property.

Example

• Whether the TM accepts 00011 is a nontrivial property. Some TMs accept 00011 and others don't.
• Whether the TM accepts infinitely many strings is a nontrivial property. Some TMs accept infinitely many strings, and some only accept finitely many strings (or even zero strings).
• Whether the TM has a reject state is a trivial property. All TMs have a reject state
• Whether the TM accepts uncountaby many strings is a trivial property. All languages contain a countable number of strings, so no TMs have this property.

Theorem

Rice's Theorem No functional and nontrivial property of Turing Machines is decidable.

Example

None of the following languages is decidable:

• \(\mathit{NE}_\mathrm{TM} = \{\ \langle M\rangle\ |\ L(M)\not=\emptyset\ \}\)
• \(\mathit{E}_\mathrm{TM} = \{\ \langle M\rangle\ |\ L(M)=\emptyset\ \}\)
• \(\mathit{ALL}_\mathrm{TM} = \{\ \langle M\rangle\ |\ L(M)=\Sigma^{*}\ \}\)
• \(\mathit{Accepts}{-}\epsilon = \{\ \langle M\rangle\ |\ \epsilon\in L(M)\ \}\)
• \(\mathtt{abba}{-}\mathit{fanatics} = \{\ \ \langle M\rangle\ |\ L(M) = \{\mathtt{abba}\}\ \}\)
• \(\mathit{DFA{-}like}=\{\ \langle M\rangle\\ |\ L(M) \mathrm{~is~regular}\ \}\)
• \(\{\ \langle M\rangle\ |\ L(M) \mathrm{~is~infinite}\ \}\)

Proof: by Rice's Theorem.

Warning!

Rice's Theorem is so easy to apply, it can be tempting to overuse it.

Example

Rice's Theorem doesn't apply to languages like the following:

• \(A_\mathrm{TM} = \{\ \langle M, w\rangle\ \ |\ \ w\in L(M)\ \}\) \ This is a set of pairs, not a set of TMs.
• \(\mathit{EQ}_\mathrm{TM} = \{\ \langle M_1, M_2\rangle\ |\ L(M_1)=L(M_2)\ \}\) This is another set of pairs of TMs, not a set of TMs.
• \(\{\ \langle M\rangle\ |\ \ M~\mathrm{has~at~least~37~states}\ \}\) This is a set of TMs, but not a functional property.
• \(\{\ \langle M\rangle\ |\ \ M~\mathrm{halts~on~every~input}\ \}\) This is a set of TMs, but not a functional property.

Example

Rice's Theorem tells us the following languages are not decidable, but doesn't say anything about whether they might be semidecidable or not.

• \(\mathit{NE}_\mathrm{TM} = \{\ \langle M\rangle\ |\ L(M)\not=\emptyset\ \}\)
• \(\mathit{E}_\mathrm{TM} = \{\ \langle M\rangle\ |\ L(M)=\emptyset\ \}\)
• \(\mathit{ALL}_\mathrm{TM} = \{\ \langle M\rangle\ |\ L(M)=\Sigma^{*}\ \}\)
• \(\mathit{Accepts}{-}\epsilon = \{\ \langle M\rangle\ |\ \epsilon\in L(M)\ \}\)
• \(\mathtt{abba}{-}\mathit{fanatics} = \{\ \ \langle M\rangle\ |\ L(M) = \{\mathtt{abba}\}\ \}\)
• \(\mathit{DFA{-}like}=\{\ \langle M\rangle\ \ |\ \ L(M) \mathrm{~is~regular}\ \}\)
• \(\{\ \langle M\rangle\ |\ L(M) \mathrm{~is~infinite}\ \}\)

Two of these undecidable languages are semidecidable and the rest are not semidecidable, but we can't prove this with Rice's Theorem.

Proving Rice's Theorem

Proof

Rice's Theorem No functional and nontrivial property of Turing Machines is decidable.

Proof:

Let \(L\) be a set of TMs having some nontrivial, functional property.

To show: \(A_\mathrm{TM} \leq_m L\).

Without loss of generality, \(N\not\in L\) where \(N\) is some always-reject TM. If \(N\in L\), then we restart the proof to show \(L^c\) is not decidable. It will then follow that \(L\) is not decidable.

Let \(Y\in L\) be some TM with the property. \(L\) contains TMs having some nontrivial property, so there's at least one TM in \(L\).

Let \(f\) be the function that turns \(\langle M,w\rangle\) into (code for) a TM \(M'\) that takes an input \(x\) and accepts \(x\) if \(Y\) accepts \(x\) and \(M\) accepts \(w\).

• If \(\langle M,w\rangle\in A_\mathrm{TM}\), then \(L(M') = L(Y)\), so \(\langle M'\rangle \in L\). \(L\) is defined with a functional property, so since \(Y\in L\) and \(L(M') = L(Y)\), it must be that \(\langle M'\rangle \in L\).
• If \(\langle M,w\rangle\not\in A_\mathrm{TM}\), then \(L(M') = \emptyset = L(N)\), so \(\langle M'\rangle \not\in L\). \(L\) is defined with a functional property, so since \(N\not\in L\) and \(L(M') = L(N)\), it must be that \(\langle M'\rangle \not\in L\).

So \(\langle M,w\rangle\in A_\mathrm{TM}\) if and only if \(f(\langle M,w\rangle) = M'\in L\), as required.

Previous: 6.21 Mapping Reductions

Next: Computational Histories