Rice's Theorem

493 views

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

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
0
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?
0

see this..hope this clears your doubt

http://gatecse.in/rices-theorem/

0
0
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
1
165 views
What is monotonic and non-monotonic property. Please explain the second postulate of Rice's Theorem.