GATE 2016 CS (CS2) – Question 54
Let L₁={⟨M⟩: M takes at least 2016 steps on some input}, L₂={⟨M⟩: M takes at least 2016 steps on all inputs}, L₃={⟨M⟩: M accepts ε}, with ⟨M⟩ encoding a Turing machine. Which holds?
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (C) L₁,L₂ recursive; L₃ not recursive
Explanation
During a fixed 2016 steps, M can inspect only a bounded input prefix. Enumerate finitely many relevant prefixes, including shorter inputs and end blanks, and simulate that many steps. This decides both the existential and universal bounded-runtime tests, so L₁,L₂ are recursive. Acceptance of ε has no fixed time bound and is undecidable by reduction from machine acceptance. Select C.