Q39

MCQ2 marks, −0.67

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?

(A)

Both $L_1$ and $L_2$ are decidable

(B)

$L_1$ is decidable and $L_2$ is undecidable

(C)

$L_1$ is undecidable and $L_2$ is decidable

(D)

Both $L_1$ and $L_2$ are undecidable

Loading…