Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
Your algorithm is correct. When you try to apply Rice's theorem, what property of languages are you using? – Yuval Filmus Feb 27 '11 at 21:33
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. – user7572 Feb 27 '11 at 21:48

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.