in Theory of Computation recategorized by
4,622 views
8 votes
8 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 recategorized by
by
4.6k views

1 comment

0
0

5 Answers

13 votes
13 votes
Best answer

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

4 Comments

decidable, considering the fact we can always force input to take more than 2021 on any turning machine. just add redundant transitions/states.
explain what exactly?

1
1

@palashbehra5 fortunately understood with what you explained to anupam :) Thanks.

0
0

@KineticKarm did you get reason for

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.

0
0
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

1 comment

Correct...
0
0
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