GATEverse
← GATE CSE 2020

Q26

MCQ2 marks, −0.67

Which of the following languages are undecidable? Note that ⟨M⟩\left \langle M \right \rangle indicates encoding of the Turing machine M. 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}\}

Sign in to save attempts.

Loading…