Log In
1 vote

I mean how it is a trivial property, we can write Tyes ( TM having even states) and Tno ( TM having odd states) for it.Can Turing machine can never have odd number of states? 

in Theory of Computation 115 views

1 Answer

2 votes
We can make every recursively enumerable language to follow this property by doing a little modification which is that we can add a useless state in case of TM with odd no of states due to which they will also have an even number of states. Hence for each of the recursively enumerable languages, we can have TM correspond to them having an even number of states thereby making it a trivial property.

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 130 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 177 views
0 votes
0 answers
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 ... 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 ?
asked Oct 28, 2017 in Theory of Computation Salazar 262 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 261 views