Project ForgeConsider the following languages, where for each Turing machine M, ⟨M⟩ denotes a specific encoding of M: L1={⟨M⟩ | M takes at least 2016 steps on some input}, L2={⟨M⟩ | M takes at least 2016 steps on all inputs}, L3={⟨M⟩ | M accepts ε}. Which one of the following is TRUE?
- AL1 is recursive and L2, L3 are not recursive
- BL2 is recursive and L1, L3 are not recursive
- L1, L2 are recursive and L3 is not recursive
- DL1, L2, L3 are recursive
Explanation
For L1 and L2, a Turing machine's behavior over its first 2016 computation steps can only ever depend on (at most) the first 2016 cells of input it could possibly read — so checking whether SOME input causes ≥2016 steps (L1), or whether ALL inputs do (L2), reduces to a FINITE, bounded simulation over all inputs of length ≤2016, each run for at most 2016 steps — making both decidable (recursive). L3 (does M accept the specific string ε?) is an instance of the general acceptance problem, which is undecidable by Rice's theorem — a non-trivial semantic property of the language M accepts.
Source: GATE CS 2016 (Session 2 / Set B) (2016)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.