# Decidability of a given language

$L_1=\{ ⟨M⟩ ∣M$ takes at least 2016 steps on some input$\}$

the answer says $L_1$ is recursive.

I am stuck at one point and i am wasting my time on it here for $L_1$ if we are given a set of to see if it takes at least 2016 steps I can use dovetailing idea and say yes for some inputs here string length doesn't matter right? for the complement of this language for $L_1$ COMPLEMENT, I will have encodings of that take less than 2016 steps on all inputs how will I check this? if strings of length &n& are taking less than 2016 steps then obviously all the $n+1$ will take less than 2016 to halt is it that way?

• Hint: $L_1 = \{ M \mid |x| < 2016$ and $M(x)$ runs for at least 2016 steps $\} \cup$ $\{ M \mid |x| = 2016, y \in \Sigma^*$ and $M(xy)$ runs for at least 2016 steps $\}$. The first set is clearly recursive; in order to prove that the second set is also recursive the "difficult part" is to prove that if $|x|=2016$ then $M(x)$ runs for at least 2016 steps if and only if $\forall y \; M(xy)$ runs for at least 2016 steps ....