retagged by
9,786 views
14 votes
14 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
retagged by

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

15 votes
15 votes
2 answers
6
Arjun asked Feb 18, 2021
4,185 views
Consider the following language:$$L= \{ w \in \{0,1\}^* \mid w \text{ ends with the substring } 011 \}$$Which one of the following deterministic finite automata accepts $...
13 votes
13 votes
5 answers
8
Arjun asked Feb 18, 2021
8,023 views
In an undirected connected planar graph $G$, there are eight vertices and five faces. The number of edges in $G$ is _________.