Which of the following is recursive

Question

Consider below two Languages

$L1=\{<M>|$M takes atleast 2000 steps on some input $\}$

$L2=\{<M>|$M takes atleast 2000 steps on all inputs$\}$

Where for each Turing machine M, $<M>$ denotes specific encoding of M.

Here I think both are recursive, because let's say I bound the number of steps the Turing machine runs to 2000, then Turing machine will only be able to process inputs of length atmost 2000.

Now, there are finite number of inputs of length 2000, I can check whether for all such inputs, my Turing machine is making 2000 steps or not.This answer L2.

And when L2 is answered, I have an answer to L1, making L1 and L2 both recursive.

Am I correct in my reasoning?

Answer 1

No, your reasoning is not correct, but I think you are very close to a correct answer.

A Turing machine in 2000 steps can only read the first 2000 symbols in the input tape, but is not forced to reject a longer input. In fact, it can accept it. So, the TM can process longer inputs, but its behavior is determined by the first 2000 symbols on the tape.

If $x$ and $y$ are words which are identical on their first 2000 symbols, then they are both accepted/rejected/neither in 2000 steps.

Because of this, we can partition the possible inputs according to their first 2000 symbols. For each of the finitely many partitions, we can extract any element and test for that one, only.

So, our decision procedure is the one given by the OP. The argument for correctness is a bit different, though.