Q44

MCQ2 marks, −0.67

Consider the following languages. $L_{1} = \left\{\left\langle M \right\rangle \mid M \text{ takes at least 2016 steps on some input} \right\}$ , $L_{2} = \left\{\left\langle M \right\rangle \mid M \text { takes at least 2016 steps on all inputs} \right\}$ and $L_{3} = \left\{\left\langle M \right\rangle \mid M \ \text {accepts }\epsilon\right\}$ , where for each Turing machine $M, \left\langle M \right\rangle$ denotes a specific encoding of $M$ . Which one of the following is TRUE?

(A)

$L_{1}$ is recursive and $L_{2}, L_{3}$ are not recursive

(B)

$L_{2}$ is recursive and $L_{1}, L_{3}$ are not recursive

(C)

$L_{1}, L_{2}$ are recursive and $L_{3}$ is not recursive

(D)

$L_{1}, L_{2}, L_{3}$ are recursive

Loading…