Consider the following languages. \(L_{1} = \left\{\left\langle M…

PYQ GATE 2016

Consider the following languages.

L1={⟨M⟩∣M takes at least 2016 steps on some input}L_{1} = \left\{\left\langle M \right\rangle \mid M \text{ takes at least 2016 steps on some input} \right\}

L2={⟨M⟩∣M takes at least 2016 steps on all inputs}L_{2} = \left\{\left\langle M \right\rangle \mid M \text { takes at least 2016 steps on all inputs} \right\}

L3={⟨M⟩∣M accepts ϵ}L_{3} = \left\{\left\langle M \right\rangle \mid M \ \text {accepts }\epsilon\right\}

where for each Turing machine MM, ⟨M⟩\left\langle M \right\rangle denotes a specific encoding of MM. Which one of the following is TRUE?

  1. A.

    L1L_1 is recursive and L2,L3L_2,L_3 are not recursive

  2. B.

    L2L_2 is recursive and L1,L3L_1,L_3 are not recursive

  3. C.

    L1,L2L_1,L_2 are recursive and L3L_3 is not recursive

  4. D.

    L1,L2,L3L_1,L_2,L_3 are recursive

Attempted by 125 students.

Sign up free to check your answer

Sign up free

Explore the full course: Theory Of Computation

Loading lesson…