For a Turing machine $M$, $\langle M \rangle$ denotes an encoding of $M$. Consider the following two languages. $L_1 = \{\langle M \rangle \mid M \text{ takes more than 2021 steps on all inputs}\}$ $L_2 = \{\langle M \rangle \mid M \text{ takes more than 2021 steps on some input}\}$ Which one of the following options is correct?
Correct answer: (A) Both $L_1$ and $L_2$ are decidable.
Explanation
Within 2021 steps M can read at most 2021 input symbols, so it suffices to simulate M for 2021 steps on the finitely many inputs of length at most 2021. Both properties are therefore decidable.
More Turing Machines and Undecidability questions
GATE 2020 CS Q36– Which of the following languages are undecidable? Note that M indicates encoding of the…
GATE 2019 CS Q44– Consider the following sets: S1. Set of all recursively enumerable languages over the…
GATE 2018 CS Q17– The set of all recursively enumerable languages is
GATE 2018 CS Q46– Consider the following problems. L(G) denotes the language generated by a grammar G. L(M)…
GATE 2015 CS (CS1) Q28– For any two languages L 1 and L 2 such that L 1 is context-free and L 2 is recursively…
GATE 2016 CS (CS1) Q27– Which of the following decision problems are undecidable? I. Given NFAs N 1 and N 2, is…