Gate2020 cs Q65

0. Which of the following languages are undecidable? Note that 〈M〉 indicates encoding of the Turing machine M.
L₁ = {〈M〉⏐L(M) = φ]
L₂ = {〈M, w, q〉⏐M on input w reaches state q in exactly 100 steps}
L₃ = {〈M〉⏐L(M) is not recursive)
L₄ = {〈M〉⏐L(M) contains at least 21 members)

Answer
Comment
Array

Option : C
Explanation :
L₁ L(m) = ϕ ⇒ emptiness problem of TM.
TM is undecidable under emptiness.
L₂ = where a TM visits a particular state in finite steps in decidable, as we can do this with UTM.
L₃ = 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₄ = Undecidable problem using rice-theorem.
Hence, L₁, L₃, and L₄ are undecidable.

Forgot your password?

I agree with the Terms.