Turing Machine

 Question 1

 A L1 is recursive and L2, L3 are not recursive B L2 is recursive and L1, L3 are not recursive C L1, L2 are recursive and L3 is not recursive D L1, L2, L3 are recursive
Theory-of-Computation       Turing Machine       GATE 2016 set-2
Question 1 Explanation:
L1 is recursive: Since counting any number of steps can be always decided. We can simulate TM (M) whether it takes more than 2016 steps on some input string, which has length upto 2016. If it happens then reached to accepting (YES) state else reject (NO).
L2 is recursive: Similarly, we can simulate TM (M) whether it takes more than 2016 steps on each input string which has length upto 2016, If it happens then reached to accepting (YES) state else reject (NO).
L3 is not recursive: If L3 is recursive then we must have a Turing machine for L3, which accept epsilon and reject all strings and always HALT. Since Halting of Turing machine can’t be guaranteed in all the case, hence this language is not recursive.
 Question 2
Let <M> be the encoding of a Turing machine as a string over Σ = {0, 1}  Let L = {<M> |M is a Turing machine that accepts a string of length 2014}. Then, L is
 A decidable and recursively enumerable B undecidable but recursively enumerable C undecidable and not recursively enumerable D decidable but not recursively enumerable
Theory-of-Computation       Turing Machine       Gate 2014 Set -02
Question 2 Explanation:
If L is recursive language then there must exist a Turing Machine which always HALT for every case (either acceptance or rejectance of string). Let the Turing Machine for L is M1.
Now, since total number of strings of length 2014 is finite, so M1 will run the encoding of M for the string of length 2014 and if the M accept the string then M1 will halt in ACCEPT state. But if M goes for infinte loop for every string of length 2014, then M1 also will go into infinite loop. Hence language L is recursively enumerable but not recursive, as in case of rejectance halting is not guaranteed.
 Question 3

 A M does not halt on any string in (0+1)+ B M does not halt on any string in (00+1)* C M halts on all strings ending in a 0 D M halts on all strings ending in a 1
Theory-of-Computation       Turing Machine       Gate-2003
Question 3 Explanation:

Try for any string, it will not Halt for any string other than ϵ. Hence, option (A) is correct.
 Question 4

 A B C D
Theory-of-Computation       Turing Machine       Gate-2003
 Question 5
 A Theory Explanation is given below.
Theory-of-Computation       Turing Machine       Gate-2002
 Question 6

 A Theory Explanation is given below.
Theory-of-Computation       Turing Machine       Gate-2001
There are 6 questions to complete.