1,537 views
5 votes
5 votes

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

1 Answer

Best answer
6 votes
6 votes

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

Related questions

1 votes
1 votes
0 answers
1
Sumaiya23 asked Jan 23, 2018
428 views
What is monotonic and non-monotonic property. Please explain the second postulate of Rice's Theorem.