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 .
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
- 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.
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.