The document Rice Theorem Computer Science Engineering (CSE) Notes | EduRev is a part of the Computer Science Engineering (CSE) Course Theory of Computation.

All you need of Computer Science Engineering (CSE) at this link: Computer Science Engineering (CSE)

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

Offer running on EduRev: __Apply code STAYHOME200__ to get INR 200 off on our premium plan EduRev Infinity!

36 videos|39 docs|39 tests

### The Post Correspondence Problem

- Video | 14:29 min
### PPT - Turing Machines

- Doc | 27 pages
### Test: Turing Machine And Halting

- Test | 10 ques | 10 min
### Test: Programming Techniques Storage And Subroutines

- Test | 10 ques | 10 min
### Test: Multitape Turing Machines

- Test | 10 ques | 10 min

- Rice's Theorem
- Video | 02:41 min