Decidable? Turing machine runs X steps for certain input?

1.3k Views Asked by At

Question is the following language decidable:

{(M)|given input "aaaaa" Turing machine M will perform at least 1295 steps}

I would say, yes it is. Just let the Universal Turing Machine count each step, and accept if it reaches step 1295.

But is this not a case where Rice´s theorem applies? Which means that we cannot decide such a property?

1

There are 1 best solutions below

0
On

Rice's theorem cannot apply to machines, only to properties of languages (since the proof of Rice's theorem relies heavily on us being able to control the language which a machine accepts, although we have very limited control on what the machine does until it accepts).

So yes, as you've answered yourself, the language is decidable.