Which of the following languages are undecidable?? Note that ⟨M⟩ indicates the encoding of the Turing machine M.
L1 = {⟨M⟩ | L(M) = Ø}
L2 = {⟨M, w, q⟩ | M on input w reaches state q in exactly 100 step}
L3 = {⟨M⟩ | L(M) is not recursive}
L4 = {⟨M⟩ | L(M) contains at least 21 members}
L1, L3 and L4 only
L1 and L3 only
L2 and L3 only
L2, L3 and L4 only
L1 = {⟨M⟩ | L(M) = Ø}
It is popularly known as the emptiness problem and we know that the emptiness problem of a Turing machine is a non-trivial property of recursive enumerable language hence by Rice theorem, it is undecidable.
L2 = {⟨M, w, q⟩ | M on input w reaches state q in exactly 100 step}
It is a decidable language as it states that the Turing machine reaches state q in 100 steps
we can run the TM 100 times on that particular string and check.
L3 = {⟨M⟩ | L(M) is not recursive}
It is undecidable as it is a non-trivial property of Recursive Enumerable language.
L4 = {⟨M⟩ | L(M) contains at least 21 members}
It is undecidable as we cannot say whether L has exactly 21 members (non-trivial property).
