##### Rice's Theorem / trivial vs. non-trivial property

Rice's Theorem states that "Every non-trivial property of the Recursive Enumerable language is undecidable"

Now i'm really confused between a trivial and non-trivial property and how it is used to prove undecidability.

Need some clarification.

Jagmeet
8 Aug 2016 05:55 am

Consider an example {<M> | M is a TM and and L(M) = {00,11} }
The Rice's Theorem states that as this property is non-trivial property so it is undecidable. But we can say we can give this finite set to TM and find whether TM accept these strings or not. Guess what we can't find out since TM can loop forever on some strings so this is undecidable.

http://gatecse.in/rices-theorem/

Sourav Mishra
8 Aug 2016 09:07 am

Correct.

Koushik Sinha
8 Aug 2016 06:18 pm

it is not turing recognisable also. cause if we give this string to all the turing machines parallely . we dont know how many TM  will accept the languge or how many TM  reject .  ihence , it is not turing recognisable .  Rice's 2nd theorem also proves that . cause it is non-monotonic property of the language