Computer Sciences > Gate 2020 > decidability and undecidability
Which of the following languages are undecidable? Note that ⟨M⟩ indicates encoding of the Turing machine M.
L1 = { ⟨M⟩ ∣ L(M)=∅ }
L2 = { ⟨M,w,q⟩ ∣ M on input w reaches state q in exactly 100 steps }
L3 = { ⟨M⟩ ∣ L(M) is not recursive }
L4 = { ⟨M⟩ ∣ L(M) contains at least 21 members }
L1 = { ⟨M⟩ ∣ L(M)=∅ }
L2 = { ⟨M,w,q⟩ ∣ M on input w reaches state q in exactly 100 steps }
L3 = { ⟨M⟩ ∣ L(M) is not recursive }
L4 = { ⟨M⟩ ∣ L(M) contains at least 21 members }
Explanation
Correct : a
Similar Questions
What is the worst-case time complexity of insertion in an AVL tree?
Which operations on a binary search tree have O(h) complexity?
Compare search complexities of sorted array vs balanced BST.