Discussion
Consider the following languages.
\(L_{1} = \{\langle M \rangle \mid M\) takes at least 2016 steps on some input\(\}\),
\(L_{2} = \{\langle M \rangle \mid M\) takes at least 2016 steps on all inputs\(\}\) and
\(L_{3} = \{\langle M \rangle \mid M\) accepts \(\varepsilon\}\),
where for each Turing machine \(M\), \(\langle M \rangle\) denotes a specific encoding of \(M\). Which one of the following is TRUE?
Answer: C
\(L_{1}, L_{2}\) are recursive and \(L_{3}\) is not recursive.
Within its first 2016 steps a Turing machine can read at most the first 2016 or so input symbols. So whether \(M\) takes at least 2016 steps on an input depends only on that input’s first 2016 symbols, and there are finitely many such prefixes. A decider can simulate \(M\) for 2016 steps on each of them and answer whether some (for \(L_{1}\)) or all (for \(L_{2}\)) inputs reach step 2016. Both are therefore recursive.
\(L_{3}\), whether \(M\) accepts the empty string, is a non-trivial property of the language \(M\) accepts, so it is undecidable by Rice’s theorem (it is recursively enumerable, but not recursive).
The options calling \(L_{1}\) or \(L_{2}\) non-recursive overlook the bounded step count, and the option calling all three recursive ignores Rice’s theorem.
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development