Consider the following languages. \(L_{1} = \left\{\left\langle M…
2016
Consider the following languages.
\(L_{1} = \left\{\left\langle M \right\rangle \mid M \text{ takes at least 2016 steps on some input} \right\}\)
\(L_{2} = \left\{\left\langle M \right\rangle \mid M \text { takes at least 2016 steps on all inputs} \right\}\)
\(L_{3} = \left\{\left\langle M \right\rangle \mid M \ \text {accepts }\epsilon\right\}\)
where for each Turing machine \(M\), \(M, \left\langle M \right\rangle\) denotes a specific encoding of \(M\). Which one of the following is TRUE?
- A.
\(L_1\)is recursive and\(L_2,L_3\)are not recursive - B.
\(L_2\)is recursive and\(L_1,L_3\)are not recursive - C.
\(L_1,L_2\)are recursive and\(L_3\)is not recursive - D.
\(L_1,L_2,L_3\)are recursive
Attempted by 63 students.
Show answer & explanation
Correct answer: C
Answer: L1 and L2 are recursive (decidable); L3 is not recursive.
L1 — decidable: To decide whether a machine M takes at least 2016 steps on some input, note that any behavior of M in its first 2016 steps can read or visit only the first 2016 tape cells of the input. Thus if there is any input on which M runs for at least 2016 steps, there is such an input of length at most 2016. So a decider can systematically enumerate all inputs of length ≤2016 and simulate M on each for 2016 steps. If any simulation reaches step 2016 (i.e., M has not halted before that step), accept; if all simulations halt before 2016 steps, reject. This algorithm always halts, so L1 is decidable.
L2 — decidable: The property 'M takes at least 2016 steps on all inputs' is universal but again only depends on the machine's behavior in the first 2016 steps. It suffices to check every input of length ≤2016: simulate M on each such input for 2016 steps. If any simulation halts before step 2016, then M does not satisfy the property and we reject; if none halt before step 2016, accept. The finite check always finishes, so L2 is decidable.
L3 — not decidable: The language of encodings of machines that accept the empty string is the special case of the general acceptance problem with the input fixed to the empty string. It is undecidable: given any pair (M,w) one can build a machine M' that on input ε simulates M on w and accepts iff M accepts w. Deciding whether M' accepts ε would decide the general acceptance problem, which is undecidable. Therefore L3 is not recursive (though it is recursively enumerable).
A video solution is available for this question — log in and enroll to watch it.