retagged by
33,278 views
108 votes
108 votes

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\}$ and
  • $L_{3} = \left\{\left\langle M \right\rangle \mid M \ \text {accepts }\epsilon\right\}$,

where for each Turing machine $M, \left\langle M \right\rangle$ 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
retagged by

7 Answers

Best answer
109 votes
109 votes

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

$L_1$ and $L_2$ are slightly trickier as these are not describing properties of recursively enumerable languages, but rather of Turing machines. So, we can see if there is some procedure for deciding these.

For $L_1$ we can give the TM an input of length $2016$. Now, it should at least make $2016$ steps or reach the halt state before completing the input processing. The second case is possible only if the TM reaches a halt state before reaching the end of string (blank) of input, for all possible inputs of length at least $2016$ and can be decided. So, we can be sure that otherwise TM will have at least $2016$ steps making $L_1$ recursive.

$L_2$ is recursive and it is more easier to prove. For the complement of $L_2$ we need $M$ to make less than $2016$ steps for some input and we can just give it all possible inputs of length less than $2016$ and see if it reaches a halt state within $2016$ steps. Thus complement of $L_2$ is recursive $\implies L_2$ is recursive.

So, answer here is C.

edited by
148 votes
148 votes

One more possible approach:

$L_3$ is not recursive (Can be proved using Rice theorem).

Lets talk about $L_1$ and $L_2,$ and let me take $L_2$ first

$L_2= \{\langle M\rangle \mid M$ takes at least 2016 steps on all inputs$\},$

I want to check if for all strings in $\Sigma^*$ $M$ takes more than or equal to $2016$ steps or not.

First of all I will restrict number of steps in $M$ to $2016,$ and I will never run $M$ more than $2016$ steps. Because for any string, if $M$ halts (accepts then halts or rejects then halts, does not matter) in less than $2016$ steps then that string is not in $L_2.$ And if $M$ does not halt within $2016$ steps (after $2016$ steps, I am not interested whether $M$ is in infinite loop or will halt eventually) then string is in $L_2.$  

 ⟹   Number of steps to be run in $M$ is not more than $2016.$

Since, we bound the number of steps that $M$ runs on an input, then there is no point on looking at any strings that are longer
than that number, since if a TM is allowed to run for at most $c$ steps, it is not possible for that TM to “process” any input symbol beyond the $c^{th}$ symbol!

⟹   Length of input string is less than $2016.$  (If I can decide for these strings then $L_2$ is Recursive otherwise not Recursive)        And there are finite strings having length less than 2016.

Now my task reduces to :   "Take each string in this finite set and run $M$ for finite number of steps"

The number of possible inputs is finite, and the number of steps M runs on each input is finite, therefore M is guaranteed to halt and decide the language.  Hence L2 is recursive.

(If we can decide for all inputs then we can also decide for some inputs therefore $L_1$ is also recursive (Reduction), but we can think of $L_1$ as an independent problem)

$L_1=\{\langle M\rangle\mid M$ takes at least $2016$ steps on some input$\},$ 

I want to check if there exist any string in $\Sigma^*$ for which $M$ takes more than or equal to $2016$ steps.

With same reasoning I can say that we will run $M$ for finite number of steps and input string set is also finite. The only difference is, we can stop giving input once we find any string taking at least $2016$ steps, whereas in $L_2$ we have to check for all set of input strings length less than $2016.$

Therefore, $L_1$ is also recursive.

$L_1, L_2:$    Recursive

$L_3:$ Not Recursive.

C is answer.

Ref: Problem number one in this pdf: https://www.cs.rice.edu/~nakhleh/COMP481/final_review_sp06_sol.pdf .

edited by
3 votes
3 votes

Most Important Note: If Turing machine is processing continuously because of Infinite number of inputs that is not an issue, but if Turing machine is processing for infinite time for an input that is a problem.

Now lets solve the Question:

L1: <M> takes atleast 2016 steps for some input,  that is for a particular encoding of T.M. <M>, on giving an input if it takes more than or equals to 2016 steps, than that encoding will be part of that Language. But for an input if <M> halts on less than 2016 steps than it takes another input and process it, For each input TM either rejects it or accepts it. Thus it is Recursive.

L2:<M> takes atleast 2016 steps for all inputs, again <M> here, will either accept or  reject  an input in finite time, and will keep on processing infinitely for infinite inputs. Thus it is also recursive.

L3:Rice Theorem 

 

Answer:

Related questions