GATE CSE 2016 Set 2 | Question: 44

Question

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?

• 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

Comments

Very good question.

Related questions - 

https://cs.stackexchange.com/questions/3101/is-the-set-of-turing-machines-which-stops-in-at-most-50-steps-on-all-inputs-dec

https://gateoverflow.in/1994/gate2014-2-35

https://gateoverflow.in/66/consider-the-following-languages

https://gateoverflow.in/151057/langle-rangle-there-exist-input-whose-length-than-which-halts%24#c151084

---

@ Sachin Mittal 1 but I read somewhere that Rice’s theorem cannot be applied when any characteristics of machine is being described. I mean we use it only when any characteristics of language is being told. So why here, did you use Rice’s theorem?

---

Related resource: http://cse.iitkgp.ac.in/~abhij/course/theory/FLAT/Spring21/slides/decidable-handout.pdf

Answer 1

$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.

Comments

@Arjun sir  i am stuck at one point and i am wasting my time on it here for L1 if we are given a set of <M> to see if it takes atleast 2016 steps I can use dovetailing idea and say yes for some inputs here string length doesn't matter right? for the complement of this language for L1 COMPLEMENT, i will have encodings of <M> that take <2016 steps on all inputs how will i check this ? if strings of length n is taking less  than 2016 steps then obviously all the n+1 will take less than 2016 to halt is it that way ?

then what are the string which i should check for ?

---

Why L3 is not recursive?

---

@Arjun sir,for the  L1 and L2 can we think like this ...i.e applying dovetaling approach i.e first consider strings of length 1 and for each step increasing srtring length by 1  (2,3,... go on till 2015  length(using enumeration) and for all of these we are sure that l1 and l2 rejects(i.e rejects all the no cases) and dont consider the remaining length as it always says yes.. (therfore it says no for all the no cases and also says yes for all greater than or equal 2016)

Therfore making both l1 and l2 recursive…...Am i correct please comment sir???

Answer 2

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 .

Comments

yes, you are correct. But answer for problem for L1 need not be always "yes". TM can simply halt in 1 or 2 or before 2016 steps- there is no reason to even process the entire string. So, this condition must be checked.

---

Yes sir i agree and understood whole scenario, please check edited answer. and let me know if any mistake is still there.

---

Sachin , 

can you explain me the difference between 

this question - 

https://gateoverflow.in/1994/gate2014-2-35

and the above one.

Even the other question has finite number of strings of length 2014, so if we run each string for 2014 steps and check if it gets accepted , if any one string gets accepted print YES or if all the (finite) strings get rejected then print NO. What is the flaw in this logic ?

Why would it go into infinite loop as both steps and the number of strings (of length 2014) are finite.

---

if string length is $l$ then turing m/c can take any number of steps. It may go to infinite loop or it may halt after 1 step only.
Say I designed a Turing m/c to accept all strings which starts with 'a'.  Now, turing m/c will halt in one step just after checking first symbol, right ?. It is irrespective of string length.

If string length is fixed, this does not bound the steps in m/c.
But if m/c steps are bounded to "c" then it certainly makes input finite (It bounds string length to c as explained in answer.)

---

Sachin,

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 cth symbol!

So  are we rejecting all the strings greater than 2016 ? 

---

Nopes, I am not rejecting or accepting. I am not even considering.
If machine is running to $c$ steps then $\left \{ 0,1, \ldots ,c-1 \right \}$only  tape cells are significant.
Now if u ask me, What happens to a particular string of length 2020 ?, U accepted it or rejected it.
Then my answer is, "whatever happens to prefix of this string of length 2016, the same happens with this also."

---

@harsh....
see these two are different things and need to be analysed carefully.
* The gate 2014 question was asking to decide whether a given TM accepts strings of length 2014. &
* this question is asking whether a TM takes 2016 steps (on some or all). 

the first 1 is undecidable coz it can be viewed as another version of halting problem. we are asked whether a given TM will halt on input of length 2014. we can't decide. It may or may not (fall in infinite loop).
And the later question is well discussed already :)

---

Minor correction

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 or rejects) in less than 2016 steps then that string belongs to a TM that is not in L2. And if M does not halts within 2016 steps then string is belongs to a TM that is in L2 

---

@Sachin

Once we have decided the strings upto 2016 ,then how will my final set language set looks like?Does it mean that we take all the valid strings upto 2016 and keep on generating new strings of length 2017,2018 .......infinite times?

Is my understanding correct?

---

Is it required to give all the strings from 0 to 2016 length.?I think if we give string of length =2016,it will be able to solve the problem.Because if smaller length is getting rejected,it will always be some prefix of some 2016 length string,it will cause that also to be rejected.So this way we can check if all strings are taking 2016 steps.

To check if some input taking atleast one step,then also i can take only 2016 length input strings instead of all length from 0 to 2016.Because of some smaller length is taking more than 2016 than larger length will also do the same

---

@rahul sharma 5

I don't think we can conclude that,

See what I got is:  you are trying to say that if we have a 2016 length string that is taking 2016 steps of machine. Then no need to check any string for length <2016 since it is bound to take 2016 steps.

For example : If we have a TM for aⁿbⁿcⁿ

ip1: aaa (TM take 1 step and halts ){Why ? Becoz first it sees an 'a' make it as 'x' eg,  then it goes forward in search of corressponding 'b' , doesnot find any so halts on reject state}

ip2: aaaaaaaa..672..bbbbbb....672.....cccccc...672 (Total length :: 2016{672*3} )

Now,here TM takes 2016 steps

Hence, we cannot conclude that if a string is taking 2016 steps then every prefix of it will take 2016 steps.

So, we need to check for all the inputs of length <=2016.

---

@rahul sharma 5

Regarding your statement : Because of some smaller length is taking more than 2016 than larger length will also do the same

This will be true only if the smaller length string  considered is a prefix of the larger length string.

See what I mean to say eg the TM may hang on i/p say aa (so taking more than 2016 steps)  but the TM may accept baa(So taking less than 2016 steps)

PS: here I am not considering any particular TM just taking random senarios.

---

I agree with your examples.Please check the following points

1. For the first part, we just need 2016 length strings only.Because 2016 strings if processed till end then will take atleast 2016 steps.But if these are not taking 2016 steps,it means these have taken at most 2015 steps,which means string is not processed completely as the condition becomes hopeless in between.So every 2017 string will have 2016 as prefix and we know 2016 string behavior,if they didn't take 2016 steps ,then 2017 will also not take.

Now in this case we don't need to process strings of <2016 length.Why? Because if string less than 2016 is taking more than 2016 steps,then it will also cause string of length 2016 length to take atleast 2016.(i am assuming the smaller string here is prefix of 2016.)

2. For second case we can not leave any string ,we have to check all 2016 string.It may be poss bile that less than 2016 is accepted and 2016 is rejected.

3. I have confusion in 2nd part of question.Now it says that every input should take atleast 2016 steps.Now assume i check only for 1  bit string that if they are taking 2016 steps or not.If yes,then all 2 length  or more are made from this 1 length only.so they will also take more than 2016 steps.If 1 length is taking less than 2016 steps.That means there is input which took less than 2016 steps.Hence No will be answer to decision problem.Please clear this point.

---

@rahul you are correct.

---

Sir,is third point correct?By checking just one bit input can i conclude the answer for second part of the question?

---

@rahul, writiing ur point again-

".Now assume i check only for 1  bit string that if they are taking 2016 steps or not.If yes,then all 2 length  or more are made from this 1 length only."

u mean if 1 bit string is taking 2016 steps then all 2 or more will take atleast 2016 steps? 

why so ?

lets say I design my turing m/c like this- If after 1 bit, it sees Blank then I am going left (back to my input string) and then again right and I do it 2016 times or any times. BUT if i see any symbol other than Blank then it stops. then it is taking only 2 steps for 2 length but 2016 steps for 1 length.

Now U might argue that why my reasoning in answer (or comment) is valid ?,  bcoz I am running m/c 2016 steps and hence I am not letting my m/c see Blank symbol in 2016 length string. and hence I can say whatever behavior my m/c is showing to 2016 length string, same will be shown to 2017 and so on bcoz at time of 2016 input length, I did not let m/c see after 2016 alphabates (after that is Blank symbol).

---

If going by the example given by Sachin sir above then even for the first part we need to check all strings of length 2016 because it may be the case that the m/c takes 2016 steps for input of length <2016 and not take 2016 steps for input of length=2016.

Quoting same example above :

lets say I design my turing m/c like this- If after 1 bit, it sees Blank then I am going left (back to my input string) and then again right and I do it 2016 times or any times. BUT if i see any symbol other than Blank then it stops. then it is taking only 2 steps for 2 length(or even greater lengths eg 2016 length input) but 2016 steps for 1 length.

---

Then as per this logic,the answer to this https://cs.stackexchange.com/questions/3101/is-the-set-of-turing-machines-which-stop-in-at-most-50-steps-on-all-inputs-deci is not correct? Because 1 length can take infinite step even if 50 length string takes 50 steps at most?

Even Arjun sir answer for part a considers only 2016 length string. 

---

@rahul

I went through this :  https://cs.stackexchange.com/questions/3101/is-the-set-of-turing-machines-which-stop-in-at-most-50-steps-on-all-inputs-deci

Answer is absolutely correct.

Basic logic there : 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 cth symbol!

So, that's why there we are not checking all the input strings( which is an infinite set)

but, we are checking only input strings of length<=50(which is finite set) --> Making the problem Decidable.

Now, there are 2 answers in the link :

In the first one ,it is not very clear that the person answering meant <=50 or =50 . Because he proved only for =50.

In the Second answer,

(and thus we can just test each input with a length of at most 50 symbols on each such automaton)

makes clear he meant <=50.

---

Yeah.I checked the first one only:)

---

@Sachin. when we will check on all inputs of upto 2016, then when we have 2016 string ,it can have 2016 th symbol as blank or it may be non blank,we will check all combinations.Am i correct?

Because in case we are checking all upto  2016 length strings should take at least 2016 steps,then 2015 nonblank followed by blank is a valid combinations and we need to check that also.Correct?

---

@ Sachin Mittal 1  your solutions are really good ...  always

---

@Sachin Mittal 1 

in your answer you have written

...if M halts in less than 2016 steps then that string is not in L2....

how can the string be in L2

L2 is the language of encodings of TM's which takes at least 2016 steps for all inputs..

isn't it??

 

---

@Sachin Mittal 1

@VS

@rahul sharma 5

can we conclude that if input string is of length 2016 or more then it will take at least 2016 steps??

---

yes @jlimbasiya

if input string length is X then at least X steps is must must must....as , one character at a time a machine checks...THIS IS KIND OF IDENTICAL TO 1 SYMBOL LOOKAHEAD ,,

1 MACHINE STATE TAKES 1 SYMBOL OR CHECKS 1 SUMBOL AT A TIME

---

What is M is a Turing machine with a STAY option, if it stay at the same position at a partiqular input, then can we say it has taken STEPS??

---

Great Answer!

---

@Sachin Mittal 1 sir in the answer you said that a string will not be part of L2 and L1 but actually the TM <m> will not be part of L2 and L1 right?

Answer 3

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 

 

Comments

can you give a example where TM process infinite time for a input.

Answer 4

For $L_1:$

For $L_2:$

Source: http://cse.iitkgp.ac.in/~abhij/course/theory/FLAT/Spring21/slides/decidable-handout.pdf