$$L_1= \{\langle M \rangle \mid \text{\(M\) takes at least 2016 steps on all inputs} \}$$

Is this language decidable?

I will write my way of understanding it. Please answer it in the way I understand & tell if my understanding is wrong.

It means L1 is a language, which includes all such Turing machines, which takes at least 2016 steps on all inputs. So we need to say it is decidable or not...

We are talking about which machine? We are talking about that machine whose language is L1. Other TMs are input to the new turing machine as encoding of 0 &1. We need to say for all inputs (for all Turing machine encodings) the new turing machine halts or not. When it will halt? When the new turing machine can either say..."Yes, the turing machine I am considering took at least 2016 steps but still it is on progress"...it also can say "No, the turing machine you gave me went to final state before 2016 steps" If it will say either of this, then the new turing machine, language L1 is decidable.

When it will be undecidable? When the new turing machine is still on progress unable to say yes or no. So solution is run new Turing machine for 2016 steps only. If it is saying "yes, the other turing machine halted...or the other turing machine did not halt."... then for both answer our new turing machine will halt... It is simple to understand that the new turing machine will always halt... bcz it's task is just to check the other turing machine halted or not within 2016 steps.


1 Answer 1


A Turing machine only sees (at most) the first 2015 symbols of the input in its first 2015 steps. Hence whether it stops within 2015 steps depends only on the first 2015 symbols of the input. This gives an algorithm for deciding $L_1$: run the input machine $M$ on all inputs of length at most 2015, and check whether any of them stops within 2015 steps. If so, reject. Otherwise, accept.

  • $\begingroup$ sir Thank you Please say is the answer written by me correct? I want to know if my understanding is correct or I am confused. $\endgroup$ Commented Jul 24, 2017 at 13:50
  • $\begingroup$ Unfortunately I am unable to understand your solution. $\endgroup$ Commented Jul 24, 2017 at 14:02
  • $\begingroup$ @YuvalFilmus:- We can generate all the string of length 2015 instead of generating smaller length strings(at most 2015).Because if smaller length string is getting rejected then it will always be prefix of some string of 2015 length.Am i missing something here ? $\endgroup$ Commented Aug 5, 2017 at 0:32
  • $\begingroup$ @rahulsharma There's no big difference. $\endgroup$ Commented Aug 5, 2017 at 7:14
  • 1
    $\begingroup$ @RookieCookie Right, the output depends only on the first 2015 symbols of the input. $\endgroup$ Commented Jun 8, 2023 at 2:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.