Question

Consider the following languages:

• L₁ = { ⟨M⟩ | M takes at least 2016 steps on some inputs}
• L₂ = { ⟨M⟩ | M takes at least 2016 steps on all inputs}
• L₃ = { ⟨M⟩ | M accepts ε} where for each turning machine M, ⟨M⟩ denotes a specific encoding of M.Which one of the following is TRUE?

Answer 1

L₃ = {M | ε ∈ L(M)}
Since the question is a non-trivial question RE language, it is undecidable by Rice's theorem.
So L₃ is not recursive.
L₁ ,L₂ are decidable (recursive), since 2016 is finite and that many steps can be simulated on a TM in finite time.