Which of the following languages are undecidable? Note that \(⟨M⟩\) indicates…

PYQ GATE 2020

Which of the following languages are undecidable? Note that ⟨M⟩⟨M⟩ indicates encoding of the Turing machine MM.

L1={⟨M⟩∣L(M)=∅}L_1 = \{\left \langle M \right \rangle \mid L(M) = \varnothing \}

L2={⟨M,w,q⟩∣M on input w reaches state q in exactly 100 steps}L_2= \{\left \langle M,w,q \right \rangle \mid M \text{ on input } w \text{ reaches state } q \text{ in exactly } 100 \text{ steps}\}

L3={⟨M⟩∣L(M) is not recursive}L_3= \{\left \langle M \right \rangle \mid L (M) \text{ is not recursive}\}

\(L_4= \{\left \langle M \right \rangle \mid L(M) \text{contains at least \(21\) members}\}\)

  1. A.

    L1L_1, L3L_3, and L4L_4 only

  2. B.

    L1L_1 and L3L_3 only

  3. C.

    L2L_2 and L3L_3 only

  4. D.

    L2L_2, L3L_3, and L4L_4 only

Attempted by 135 students.

Sign up free to check your answer

Sign up free

Explore the full course: Zero To Hero

Loading lesson…