Consider the following languages.

$L_1 = \{<M> \mid M \text{ takes at least 2016 steps on some input}\}$,

$L_2 = \{<M> \mid M \text{ takes at least 2016 steps on all inputs}\}$ and

$L_3 = \{<M> \mid M \text{ accepts } ε\}$,

where for each Turing machine $M, <M>$ denotes a specific encoding of $M$. Which one of the following is TRUE?

  1. $L_1$ is recursive and $L_2, L_3$ are not recursive
  2. $L_2$ is recursive and $L_1, L_3$ are not recursive
  3. $L_1, L_2$ are recursive and $L_3$ is not recursive
  4. $L_1, L_2, L_3$ are recursive

My attempt :

Official answer is given option $(3)$. $L_3$ is not recursive as it asks if $L(M)$ contains $\varepsilon$ which is a non-trivial property of r.e. languages and hence undecidable as per Rice's theorem.

Can you explain in formal way, please? How we prove that $L_1, L_2$ are recursive languages?

  • 1
    $\begingroup$ This question is okay here, but it would also be very okay at Computer Science. Just saying. $\endgroup$ – k.stm Mar 4 '16 at 14:04

The idea is that the property of making at least $2016$ moves on a particular input depends only on the first $2016$ symbols. So in order to decide $L_1$, it is sufficient to check all words $w$ of length at most $2016$ and simulate at most $2016$ steps of $M$ on each. If there is at least one word on which the $2016$-th step has been reached, we accept. All this can be done in finite time. To decide $L_2$, we accept if we reach the $2016$-th step on all words of length at most $2016$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.