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 }
Correct : a
Similar Questions
A palindrome is a word that reads the same forwards and backwards. In a game
of words, a player has the following two plates painted with letters.
From...
Which number does not belong in the series below?
2, 5, 10, 17, 26, 37, 50, 64
Choose the word that is opposite in meaning to the word “coherent”.
Total Unique Visitors
Loading......