Rice’s Theorem

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.


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.

Visualizing R

Using R, build another TM D as follows

On input <M, w>

  1. Construct a new TM U 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.
  2. 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.


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.

Leave a Reply

Your email address will not be published. Required fields are marked *