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$