# Is it decidable if a TM takes at least 2016 steps on all inputs?

$$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.

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.