###### Theory-of-Computation

October 6, 2023###### UGC NET Dec-2020 and June-2021 Paper-2

October 6, 2023# Theory-of-Computation

Question 8 |

Which of the following languages are undecidable? Note that indicates encoding of the Turing machine M.

- L

_{1}= | L(M) = Φ}

L

_{2}= {| M on input w reaches state q in exactly 100 steps}

L

_{3}= {| L(M) is not recursive}

L

_{4}= {| L(M) contains at least 21 members}

L _{2} and L_{3} only
| |

L _{1} and L_{3} only
| |

L _{2}, L_{3} and L_{4} only | |

L _{1}, L_{3} and L_{4} only |

Question 8 Explanation:

L

Only L

_{1}is undecidable as emptiness problem of Turing machine is undecidable. L_{3}is undecidable since there is no algorithm to check whether a given TM accept recursive language. L_{4}is undecidable as it is similar to membership problem.Only L

_{3}is decidable. We can check whether a given TM reach state q in exactly 100 steps or not. Here we have to check only upto 100 steps, so here is not any case of going to infinite loop.Correct Answer: D

Question 8 Explanation:

L

Only L

_{1}is undecidable as emptiness problem of Turing machine is undecidable. L_{3}is undecidable since there is no algorithm to check whether a given TM accept recursive language. L_{4}is undecidable as it is similar to membership problem.Only L

_{3}is decidable. We can check whether a given TM reach state q in exactly 100 steps or not. Here we have to check only upto 100 steps, so here is not any case of going to infinite loop. Subscribe

Login

0 Comments