Rice Theorem | Theory of Computation - Computer Science Engineering (CSE) PDF Download

Part IX. Rice Theorem

Recursive and Non-Recursive Languages
Recursive Languages
A language, L is recursive, if
it is possible to design a TM that halts in the final state to say yes if w∈L, and halts in the non-final state to say no if w ∉ L.

Recursively Enumerable Languages
A language, L is recursively enumerable, if
it is possible to design a TM that halts in the final state to say yes if w∈L, and halting cannot be guranteed if w ∉ L.
Languages that are neither Recursive nor Recursively Enumerable
A language, L is neither recursive nor recursively enumerable, if the structure of the language is such that no TM which recognises w can be designed.

12 Rice Theorem
Rice’s theorem states that
every non-trivial property of a recursively enumerable language is undecidable.

Proof
A non-trivial property is one that is possessed by some objects of a class, but not all.
For example, being a mathematician is a property that is possessed by some humans but not by all.
Some cats are black but not all. So black colour property cannot be trivially associated with cats.
Let χ be a non-trivial property that is not possessed by all recursively enumerable languages. This problem can be reduced to one consisting of a pair (M, w) such that L possesses χ iff w ∈ L(M). We take a UTM U that takes a pair (M, w); its output is yes iff χ is possessed by L.
Since L is a recursively enumerable language, there must be a TM, M_L that accepts L. Let x be a string belonging to L. Now, we design a machine M' to decide χ as shown below:

Here U is a UTM.
UTM, U takes the pair (M, w) and checks if w ∈ L(M). If the output is yes, then the machine M_L that accepts the string x starts and the output of the machine M' is yes. Thus the decidability of the problem of possessing the trivial property reduces to the problem of L_u. If the pair (M, w) ∈ L_u, then L possesses χ ; otherwise not. Since L_u is not recursive,
possession of χ by L is also not decidable.