Log In
4 votes

I am unable to understand when to apply Rice's theorem and when to not. How L2 is decidable.

in Theory of Computation 493 views

1 Answer

4 votes
Best answer

First I will explain $L_2$
$L_2$ :{<M>|M is a Turing Machine, |M| < 200 where |M|  is number of states in machine }

Rice theorem is applicable to non-trivial language property 
$L_2$ is not a language property, it is a machine structure property
so, Rice theorem is not applicable here
but it is decidable because from TM description we can determine the number of states in the TM 

$L_1$ :{<M,q>|M is a Turing Machine that visits state q on some input within 15 steps}

$L_1$ is also not a language property, but it is also not a machine structure property
so, Rice theorem is not applicable here
but it is also decidable because we can simulate the TM for 15 steps 

selected by
Thanks lokesh.Just need one clarification.

e.g:-  L={M| L(M) is xyz}

When we say language property,it means that we are saying that we are going to build a turing machine ,whose language is codes of turing machines which has xyz in its language.Language property means xyz,is it correct?

And if xyz is non trivial then it is undecidable,correct?

see this..hope this clears your doubt

Thanku so much for replying...I understood ur answer.. :)
Lokesh, how can you count the number of states a TM can visit? Or just count states from the encoding itself?

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 165 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 224 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 351 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 364 views