## Turing Machine

 Question 1
Consider the following languages.
L1 = {〈M〉|M takes at least 2016 steps on some input},
L2 = {〈M〉│M takes at least 2016 steps on all inputs} and
L3 = {〈M〉|M accepts ε},
where for each Turing machine M, 〈M〉 denotes a speciﬁc encoding of M. Which one of the following is TRUE?
 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]       Video-Explanation
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.
There is 1 question to complete.

Register Now