Question 9935 – Theory-of-Computation
December 6, 2023Question 14253 – Theory-of-Computation
December 6, 2023Question 14234 – Theory-of-Computation
For a Turing machine M, <M> denotes an encoding of M. Consider the following two languages.
L1=〈M〉|M takes more than 2021 steps on all inputs
L2=〈M〉|M takes more than 2021 steps on some input
Which one of the following options is correct?
Correct Answer: D
L1 is decidable.
We can take all strings of length zero to length 2021.
If TM takes more than 2021 steps on above inputs then definitely it will take more than 2021 steps on all input greater than length 2021.
If TM takes less than 2021 steps:
In such a case suppose TM takes less than 2021 steps (let’s say 2020 steps ) for string length 2021, 2022, 2023, then definitely TM will take 2020 steps for all input greater than 2023. Hence in both cases it is decidable.
Similarly L2 is also decidable. If we can decide for all inputs then we can decide for some inputs also.