The Gateway to Computer Science Excellence
+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 by Boss (25.6k points) | 188 views

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


Can you please give an example?Why cant we apply it here:- ,the way it was applied here

See the ans there

Please log in or register to answer this question.

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,370 answers
105,272 users