Rice's Theorem - The Beard Sage

Every non-trivial property, $P$ , of the language of Turing Machines is undecidable. This is Rice’s Theorem.

Because $P$ is non-trivial there is some Turing Machine $T$ such that $<T> \in P$ and some other Turing Machine $S$ such that $<S> \notin P$ .

Proof

$P$ is undecidable. This can be proved using contradiction.

Suppose to the contrary that that there exists a TM, $R$ , that decides $P$ . This machine takes $<M>$ as an input. It accepts if $<M> \in P$ and rejects otherwise.

Using $R$ , build another TM $D$ as follows

On input $<M, w>$

Construct a new TM as follows
1. On input $x$ , Run $M$ on $w$ .
2. If $M$ accepts $w$ , run $T$ on $x$ .
3. If $T$ accepts $x$ , accept.
Run $R$ on $U$ . If $R$ accepts $U$ (implying that $U$ has property $P$ ), accept. Else, reject.

The machine $D$ takes $<M, w>$ as an input. It accepts if $U$ satisfies the property $P$ . This implies that $U$ and $T$ share the same language. This will only hold true if $M$ accepts $w$ . In essence, this is a machine that decides $A_{TM}$ . We say that $R$ reduces to $A_{TM}$ .

Since $A_{TM}$ is undecidable, the property $P$ is also undecidable.

Example

Using Rice’s theorem makes the problem of proving the undecidability of languages pretty straightforward. You have to identify the property and prove that it is non-trivial. Consider the following problem

$\begin{equation*} CFL_{TM} = \{<M>: M \text{ is a TM whose language is a context-free language } \} \end{equation*}$

The property $P$ in this case is $L(M)$ is context-free. $P$ is indeed a property of the language of TMs because for any 2 machines $M$ and $N$ such that $L(M) = L(N)$

$\begin{equation*} <M> \in CFL_{TM} \iff L(M) \text{ is CFL } \iff L(N) \text{ is CFL } \iff <N> \in CFL_{TM} \end{equation*}$

$P$ is non-trivial because there is at least one TM that belongs to $CFL_{TM}$ (a TM that accepts $0^*$ ) and at least one TM that doesn’t belong to $CFL_{TM}$ (a TM that accepts $0^n1^n2^n$ ).

By Rice’s Theorem, $CFL_{TM}$ is undecidable.

Proof

Example

Leave a Reply Cancel reply