RICE theorem applications

Question

I am having some confusion in understanding RICE's theorem.

It says every non trivial property of RE in undecidable.

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 will halt on every input <50 and some will not?So if this is Non trivial property then why cant we apply RICE's theorem?

On other side questions like:- TM accepts at least 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 mentioned questions?

Please help me in understanding how to identify whether question is based on Rice's theorem or not?

Answer 1

The major hypothesis of Rice theorem is that you are dealing with a set which is "extensional", or "semantically closed". Formally this requires that when the encoding of a TM $M$ belongs to the set, and $N$ is a TM equivalent to $M$, then the encoding of $N$ must also belong to the set.

Equivalence here means that the TMs $M,N$ terminate on the same inputs, with the same output (including acceptance).

Conditions like "halts in 50 steps" break equivalence, in general. I.e. it is possible that $M$ halts in 10 steps with output zero on every input, yet $N$ does the same after "wasting" 100 steps. So, Rice can not be applied to these.

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

No. The property "at least five moves" is decidable. The properties "accepts a string of at least five" and "halts for every input of length <50" are NOT decidable. Indeed, these properties only care about the input/output behavior of the TM, hence if $M$ satisfies one of those, and $N$ is equivalent, then $N$ also satisfies the same property. So, Rice applies to those.

Answer 2

I think rice theorem considers non trivial property of language not Turing machines. The properties that you have mentioned are not related t languages, they are related the machines. A non trivial property for languages would be "Does the language generated by a turing machine contain string of length 10?".