4
$\begingroup$

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?

  • 3
    Oh...I guess the point is that the property is not one of the language but only of the turing machine? And Rice´s theorem only applies for languages.2011-02-27

1 Answers 1

4

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.