Theory-of-Computation
December 6, 2023Theory-of-Computation
December 6, 2023Theory-of-Computation
|
Question 4
|
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?
|
Both L1and L2 are undecidable.
|
|
|
L1is undecidable and L2is decidable.
|
|
|
L1is decidable and L2is undecidable.
|
|
|
Both L1and L2 are decidable.
|
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.
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.