0
$\begingroup$

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?

$\endgroup$
1
  • 1
    $\begingroup$ A Turing machine running in 2000 steps could accept, for example, all strings starting with 10 - of any length. $\endgroup$ Commented Dec 28, 2018 at 11:48

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

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.