Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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
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. –  user7572 Feb 27 '11 at 21:48

1 Answer 1

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|improve this answer

Your Answer

 
discard

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