in Theory of Computation
704 views
1 vote
1 vote
I need to understand when to apply RICE's theorem and when to not.

Questions like:- Turing machine makes at least five moves,It  accepts a string  input of length atleast five ,TM halts for every input on length <50 are all decidable.

But  these  are  NON TRIVIAL properties?Some TM will make 5 moves and some will not,Some can halt on every input <50 and some can not?So if this is Non trivial property then why cant we apply RICE's theorem?

I was reading Arjun's sir blog on GateCse,there will say that TM accepts atleast 10 strings is undecidable because some TM will say yes and some will say NO.Then why can't we use same concept on above metioned questions?

Please help
in Theory of Computation
704 views

3 Comments

Rice theorem is applied on non-trivial language properties .....above both properties are not language properties

0
0

Can you please give an example?Why cant we apply it here:- https://gateoverflow.in/100112/rices-theorem ,the way it was applied here http://gatecse.in/rices-theorem/

0
0
See the ans there
0
0

Please log in or register to answer this question.

Related questions