Question

Which of the following languages are undecidable? Note that ⟨M⟩ indicates encoding of the Turing machne 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)

• A. L₁ and L₃ only
• B. L₂ and L₃ only
• C. L₂, L₃ and L₄ only
• D. L₁, L₃ and L₄ only

Answer 1

The correct option is D L₁, L₃ and L₄ only

Rice's theorem applies to L₁, L₃ and L₄ since then have condition based on L(M),which are non-trivial.
L₁: L(M) = Φ is non-trivial condition becuase some Turing machines accept Φ and some don't.
L₃: L(M) = non-recursive, is non-trivial becuase some Turing machines accept non-recursive and some accept recursive.
L₄: L(M) contains at least 21 members is non-trivial since some Turing machines accept more than 21 strings, some accept less.
L₂: We cannot apply Rice's theorem since condition is not on L(M) but on M reaching a state q in exactly 100 steps which can be checked on a UTM.
So L₂ is decidable.
So, option (b). L₁, L₃ and L₄ are undecidable is correct.