in Theory of Computation
531 views
0 votes
0 votes

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 ?

in Theory of Computation
by
531 views

2 Comments

@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
1
1

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

 

0
0

1 Answer

0 votes
0 votes
Rice's theorem is not applicable in this case as Turing machines having even number of states or any number of state is not a language property but it is a machine property. This is decidable problem because it is a trivial one as we can convert any turing machine having odd number of state to a turing machine with even number of state by adding one more state.

Related questions