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

Because is non-trivial there is some Turing Machine such that and some other Turing Machine such that .

## Proof

is undecidable. This can be proved using contradiction.

Suppose to the contrary that that there exists a TM, , that decides . This machine takes as an input. It accepts if and rejects otherwise.

Using , build another TM as follows

On input

- Construct a new TM as follows
- On input , Run on .
- If accepts , run on .
- If accepts ,
*accept*.

- Run on . If accepts (implying that has property ),
*accept*. Else,*reject*.

The machine takes as an input. It accepts if satisfies the property . This implies that and share the same language. This will only hold true if accepts . In essence, this is a machine that decides . We say that reduces to .

Since is undecidable, the property 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

The property in this case is is context-free. is indeed a property of the language of TMs because for any 2 machines and such that

is non-trivial because there is at least one TM that belongs to (a TM that accepts ) and at least one TM that doesn’t belong to (a TM that accepts ).

By Rice’s Theorem, is undecidable.