## Turing Machine

Question 1 |

Consider the following languages.

L

L

L

where for each Turing machine M, 〈M〉 denotes a speciﬁc encoding of M. Which one of the following is

L

_{1}= {〈M〉|M takes at least 2016 steps on some input},L

_{2}= {〈M〉│M takes at least 2016 steps on all inputs} andL

_{3}= {〈M〉|M accepts ε},where for each Turing machine M, 〈M〉 denotes a speciﬁc encoding of M. Which one of the following is

**TRUE**?L _{1} is recursive and L_{2}, L_{3} are not recursive | |

L _{2} is recursive and L_{1}, L_{3} are not recursive | |

L _{1}, L_{2} are recursive and L_{3} is not recursive | |

L _{1}, L_{2}, L_{3} are recursive |

Question 1 Explanation:

L

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

L

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

L

If L

Since Halting of Turing machine can’t be guaranteed in all the case.

Hence this language is not recursive.

_{1}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).

L

_{2}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).

L

_{3}is not recursive:If L

_{3}is recursive then we must have a Turing machine for L_{3}, 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.