in Theory of Computation retagged by
5,770 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.8k views

1 comment

4
4

5 Answers

18 votes
18 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

12 Comments

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.

I didn’t understand the above line. Why it won’t take more than 2021 steps for input length > 2021? For example, we have a string of length 2030. Now TM halts within 2021 steps for a prefix of string having length 2021 or less, but still, we have 9 characters left, so My guess is - it is possible that to process this 9 characters TM halts after 2021 steps or never halts. Please @Arjun sir clear this doubt.

3
3

 

@ sir, why aren’t we using here Rice theorem?  

just wanted to clear- is it because the property mentioned in the question is about the machine and not about the language. You have previously mentioned in comments that Rice Theorem is applicable only for the language only. 

1
1

Yes, you got it right. Rice theorem is defined on Recursive Enumerable language (REL). See the statement of Rice theorem below.

RICE theorem: Every Non-trivial property of REL is undecidable

Here question clearly asking about the set of Turing Machines so it is nothing to do with RELs. Correct me if I am wrong.

1
1
i think it should be right
1
1
edited by

  , Yep, the above mentioned are the property of the TM, not the language it recognizes.

https://www.cs.swarthmore.edu/~fontes/cs46/20s/misc/RicesTheorem.pdf

0
0
0
0
Can anyone explain me, what about those input which have size less than 2021. Like for example, Lambda, a, b etc?
2
2

@ sir, If L2 had been “ L2={⟨M⟩∣M takes more than 2021 steps on ALL inputs} “ , Then L2 would be undecidable right?

0
0
The given que is about the working of turing machine not about the languages so Rice's theorem surely cannot apply here

In ullman it is clearly mentioned...
0
0

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