# Rice's Theorem

276 views

Example# 3 from Part-1 Rice's Theorem from https://gatecse.in/rices-theorem/ states as follows

(3) L(M) is recognized by a TM having even number of states

Sol: This is a trivial property. This set equals the set of recursively enumerable languages.

According to the previous examples, if i can find a Turing Machine which says Yes and a Turing Machine which says No, so i'll choose TNO as PHI (Empty String) and TYES as  a TM which accepts even number of states, then is it true that my L(M) is undecidable as the property is non-trivial, is my Reasoning correct ?

It seems like i can find TYES and TNO for every property then?
Can someone give me an example for which TYES and TNO cannot be found and let me know if my approach is correct ?

1
@salazar

Yes or no means ...NO should reject  everything except even number of states

And the statement says it recognises which means for yes we can find a solution..but for NO it may either reject or never halt and enter loop

and that is turing machine recognisable

When YES and NO both are clear then it is TM decidable
0

How can we apply rice theorem in this example ?.. i think "TM having even number of states" is TM property , not a language property.

## Related questions

1 vote
1
139 views
What is monotonic and non-monotonic property. Please explain the second postulate of Rice's Theorem.