# Lecture 15: General undecidability criterion

## Rice’s Theorem

We will show that every non-trivial property of languages of Turing machines is undecidable *(Rice’s theorem)*. To show this theorem, we will formalize what properties of languages are and what it means for them to be non-trivial for Turing machines.

Let \(2^{\{0,1\}^\ast}\) be the set of all languages over the binary alphabet. A **property** of languages is a subset \(P\subseteq 2^{\{0,1\}^\ast}\). We say \(L\) *satisfies* \(P\) if \(L\in P\) and we say that \(L\) *violates* \(P\) if \(L\notin P\). For example, we can choose \(P\) to be the set of languages that contain the string \(0000\).

We say that \(P\) is a **non-trivial** property of languages of Turing machines if there exists Turing machines \(M_Y\) and \(M_N\) such that \(L(M_Y)\) satisfies the property and \(L(M_N)\) violates the property. Here is an example of a property that is non-trivial for languages of Turing machines, \[
P_{\mathrm{empty}} = \{ \emptyset \}.
\] The property is non-trivial because there are Turing machines that recognize the empty language and there are Turing machines that recognize a non-empty language. Here is an examples of a property that is trivial for languages of Turing machines, \[
P_{\mathrm{recognizable}} = \{ L \mid \text{$L$ is recognizable}\}.
\]

Theorem:Let \(P\) be any non-trivial property of languages of Turing machines. Then, the following language is undecidable, \[ L_P = \{ \langle M\rangle \mid \text{ $L(M)$ satisfies $P$} \}. \]

*Proof:* We distinguish two cases, \(\emptyset \in P\) and \(\emptyset \notin P\).

**Case \(\emptyset\notin P\):** In this case, we will show that \({A_{\mathrm{TM}}}\le_m L_P\), which implies that \(L_P\) is undecidable. (See the notes for lecture 14 for the proof that the acceptance problem \({A_{\mathrm{TM}}}\) is undecidable.) Let \(M_Y\) be a Turing machine such that \(L(M_Y)\in P\) satisfies \(P\). (We know it exists because \(P\) is a non-trivial property of languages of Turing machines.) Consider the computable function \(f\) that maps \(\langle M, w\rangle\) to \(\langle M'_{w} \rangle\), where \(M'_w\) is the following Turing machine:

Operation of \(M'_w\) on input \(u\):

- Simulate \(M\) on input \(w\).
- If \(M\) accepts, simulate \(M_Y\) on input \(u\) and accept if \(M_Y\) accepts.

By construction, the machine \(M'_w\) accepts on input \(u\) if and only if \(M\) accepts \(w\) and \(M_Y\) accepts \(u\). Therefore, \(L(M'_w)=L(M_Y)\) if \(M\) accepts on \(w\) and \(L(M'_w)=\emptyset\) if \(M\) does not accept \(w\). Since \(L(M_Y)\in P\) and \(\emptyset\notin P\), we see that \(L(M'_w)\) satisfies \(P\) if and only if \(M\) accepts \(w\). Thus, \(f\) is a reduction from \({A_{\mathrm{TM}}}\) to \(L_P\).

**Case \(\emptyset\in P\):** We will reduce this case to the previous case. The complement property \(\neg P\) is also a non-trivial property of languages of Turing machines and it satisfies \(\emptyset \notin \neg P\). The proof for the previous case applies and we get that \(L_{\neg P}\) is undecidable. Since \(L_P = \neg L_{\neg P}\), we can conclude that \(L_P\) is undecidable (undecidability is closed under complementation). \(\square\)