The Gateway to Computer Science Excellence
+4 votes
331 views

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
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
Thanku so much for replying...I understood ur answer.. :)
0
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
198,391 comments
105,142 users