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}?

Option 1 : L1, L3, and L4 only

The decidability problem of Turing Machines can directly be determined using Rice’s theorem.

L1 is undecidable. According to Rice’s theorem, emptiness problem of Turing machine is undecidable.

L2 is decidable. This is because here we have to check whether the Turing machine reaches a particular step ‘q’ on a given input in finite steps or not. This is a decidable problem.

L3 is undecidable. There is no algorithm to computationally determine whether a Turing machine accepts a recursive language or not. Some Turing machines may accept recursive languages, while other may not.

L4 is also undecidable. According to Rice’s theorem, membership problem of Turing machine is undecidable.