TheoryofComputation
October 6, 2023UGC NET Dec2020 and June2021 Paper2
October 6, 2023TheoryofComputation
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_{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.
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_{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.
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