retagged by
9,773 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

Best answer
21 votes
21 votes

$\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}$

Here, both $L_1$ and $L_2$ are decidable as we can have a systematic procedure in deciding them (correctly saying if an input is in $L$ or not)

For both $L_1$ and $L_2$ we have to monitor the $\textsf{TM}$ for $2021+1$ steps for all possible inputs of size $2021$ (if the input set is having $k$ alphabets we will have $k^{2020}$ possible strings which is still a finite number.)

If for all the inputs $M$ is taking more than $2021$ steps, then it means for all larger strings also it must take more than $2021$ steps and we can answer “yes” for $L_1$ or else “no”.

If for none of the inputs $M$ is taking more than $2021$ steps then it means even for any larger string $M$ won’t be taking more than $2021$ steps. So, we can answer “no” for $L_2$ or else “yes”.  

Thus we correctly decided both $L_1$ and $L_2.$

NOTE: There is intersection between 

  • “yes” case of $L_1$ and “yes” case of $L_2$
  • “no” case of $L_1$ and “yes” case of $L_2$
  • “no” case of $L_2$ and “no” case of $L_1$

but not between the “yes” case of $L_1$ and “no” case of $L_2.$

Correct Option: A.

selected by
2 votes
2 votes
Both of them have to be decidable. It is known that wd have a Turing machine that can simulate the moves of any Turing machine with an input applied to it.

In 2021 steps, note that the Tape head of a Deterministic (even if its non deterministic, we can do dovetailing) moves at the most 2021 steps to the right. Therefore for both L1 and L2 we can can do an exhaustive simulation of the TM coded as <M> over all the inputs of length upto 2022(anything greater than or equal to 2021 should do) and see if the predicate of L1 is satisfied for problem L1, and predicate of L2 is satisfied for problem L2

For L1:

M takes more than 2021 steps to halt on all inputs (iff) M takes more than 2021 steps on all the inputs of length less than or equal to 2022

 

For L2:

M takes more than 2021 steps to halt on some input (iff) M takes more than 2021 steps on some input of length less than or equal to 2022
0 votes
0 votes

The Correct answer should be A as both are decidable.

After 2021 steps (constant number of steps ) we can finally stop the machine. If the number of steps it takes is less than 2021 then also its decidable hence for all inputs we can confirm this. Hence Both the statements are correct. 

0 votes
0 votes
  1. L1: Whether the machine makes more than 2021 steps on all inputs is to be decided. For a single input it is obviously decidable, but for all inputs (which are infinite in number), how to decide it? So this language is not decidable.
  2. L2: In this case also, we have to decide whether a given TM <M> makes more than  2021 steps at least on one input. In case <M> does not make 2021 steps on any of the inputs, then how to reach the conclusion that this <M> is not in the language? So this language is also undecidable.

So ,in my view D is the right option.

Answer:

Related questions

15 votes
15 votes
2 answers
2
Arjun asked Feb 18, 2021
4,175 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
4
Arjun asked Feb 18, 2021
8,018 views
In an undirected connected planar graph $G$, there are eight vertices and five faces. The number of edges in $G$ is _________.