Log In
0 votes

Example# 3 from Part-1 Rice's Theorem from 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 276 views

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

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


Please log in or register to answer this question.

Related questions

1 vote
0 answers
What is monotonic and non-monotonic property. Please explain the second postulate of Rice's Theorem.
asked Jan 23, 2018 in Theory of Computation Sumaiya23 139 views
0 votes
0 answers
I have a doubt while understanding step 2 in proof of Rice's Theorem- According to my understanding,proof of Rice's theorem as follows ( Please suggest If something is wrong in my understanding) P is a property of languages of TM which is non-trivial and semantic. We ... at all(Same problem as ATM). Can M' take decision in finite time. Please give me some insights to I can understand this point.
asked Dec 15, 2017 in Theory of Computation Durgesh Singh 186 views
1 vote
0 answers
L = {M|M is a TM that accepts all even numbers} For the above language i can have Tyes machine which has all even numbers.And Tno as machine whose language is empty.So i can say it is undecidable. But to show it is Not RE. What should be my Tno,so that ... Tno machine?I am assuming here that the property of the language as "Only all even numbers",i guess the same has been given in the question.
asked Aug 5, 2017 in Theory of Computation rahul sharma 5 268 views
4 votes
1 answer
I am unable to understand when to apply Rice's theorem and when to not. How L2 is decidable.
asked Jan 3, 2017 in Theory of Computation Lucky sunda 428 views