$$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.
Is it decidable if a TM takes at least 2016 steps on all inputs?
computability;turing machines;undecidability