The Gateway to Computer Science Excellence
+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 by Active (4.5k points) | 331 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 

by Boss (11.6k points)
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

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,321 answers
105,142 users