in Theory of Computation retagged by
5,700 views
10 votes
10 votes

For a Turing machine $M$, $\langle M \rangle$ denotes an encoding of $M$. Consider the following two languages.

$$\begin{array}{ll} L_1 = \{ \langle M \rangle \mid M \text{ takes more than } 2021 \text{ steps on all inputs} \} \\ L_2 = \{ \langle M \rangle \mid M\text{ takes more than } 2021 \text{ steps on some input} \} \end{array}$$

Which one of the following options is correct?

  1. Both $L_1$ and $L_2$ are decidable
  2. $L_1$ is decidable  and $L_2$ is undecidable
  3. $L_1$ is undecidable  and $L_2$ is decidable
  4. Both $L_1$ and $L_2$ are undecidable
in Theory of Computation retagged by
by
5.7k views

1 comment

3
3

5 Answers

0 votes
0 votes
L1 is decidable

For all inputs having length > 2021. That is, of length 2022 or more it will take more than 2021 steps. However, of inputs of length 2021 or less, the challenge is how it should take 2022 steps or more to get it accepted. Following situations possible:

1. L1 has entries such that <M> takes more than 2021 steps. Assume, it to be deterministic. The input of length 2021 or less gets rejected. Hence, all the inputs of length greater than 2021 is accepted and present in L1.

2. By default TM 2021 epsilon transaction is defined on the TM. Hence, it will take more than 2021 steps on all inputs.

But this observation, the property of language is trivial. So, it's decidable as we can deterministically say for which input it will accept or reject.

 A similar type of observation can be shown for L2 as well
Answer:

Related questions