GATE Computer Science (CS) 2020 Solved Papers

Question : 36 of 65

Marks: +1, -0

Which of the following languages are undecidable? Note that

( {M}⟩

indicates encoding of the Turing machine M.

{L}_{1}=\{⟨ {M}⟩ {L}( {M})=\varnothing\}

{L}_{2}=\{⟨ {M}, {w}, {q}⟩ ∣ {M}

on input

{w}

reaches state

{q}

in exactly

100 {steps}\}

{L}_{3}=\{⟨ {M}⟩ {L}( {M})

is not recursive}

{L}_{4}=\{⟨ {M}⟩ ∣ {L}( {M})

contains at least 21 members

\}

Solution:

L_1

{L}( {m})=ϕ ⇒

emptiness problem of

{TM}

.
TM is undecidable under emptiness.

{L}_{2}=

where a TM visits a particular state in finite steps in decidable, as we can do this with UTM.

{L}_{3}= {L}( {m})

is non-Recursive,

Clearly from the diagram

{L}( {A}) ⇒

non recursive language accepted by

{TM}

{L}( {B}) ⇒

non-recursive language not accepted by

{TM}

∴

it is a non-trivial property, hence undecidable.

{L}_{4}=

Undecidable problem using rice-theorem.
Hence,

{L}_{1}, {L}_{3}

, and

{L}_{4}

are undecidable.

Go to Question:

Prev Question

Next Question