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

GATE · 2020 · CS · Computer Science & IT

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}\}

L4={⟨M⟩∣L(M)contains at least 21 members}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 114 students.

Sign up free to check your answer

Sign up free

Explore the full course: Gate Guidance By Sanchit Sir

Loading lesson…