Skip to content
GATEiit

GATE CSE 2020 Q36: Which Turing machine languages are undecidable

Question

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

L1={⟨M⟩∣L(M)=∅}L_1 = \{\langle M \rangle \mid L(M) = \emptyset\} L2={⟨M,w,q⟩∣M on input w reaches state q in exactly 100 steps}L_2 = \{\langle M, w, q \rangle \mid M \text{ on input } w \text{ reaches state } q \text{ in exactly 100 steps}\} L3={⟨M⟩∣L(M) is not recursive}L_3 = \{\langle M \rangle \mid L(M) \text{ is not recursive}\} L4={⟨M⟩∣L(M) contains at least 21 members}L_4 = \{\langle M \rangle \mid L(M) \text{ contains at least 21 members}\}

Try it: multiple choice: exactly one correct option

Select one option
Wrong answer costs 2/3 mark in GATE.
Show answer and explanation

Answer: A (official GATE 2020 final answer key)

Concept used: Rice's theorem: every non-trivial property of the language of a TM is undecidable; a bounded simulation is decidable.

First step: L2L_2 only needs a 100-step simulation, so it is decidable; check that the properties in L1L_1, L3L_3, L4L_4 are about L(M)L(M) and non-trivial.

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

WhatsAppDownload image

Source: official GATE 2020 CS question paper and final answer key, organised by IIT Delhi. Question paper · Answer key

More Theory of Computation PYQs

PracticePractise Theory of Computation questions →Full paperAll GATE CSE 2020 questions →