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

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

L1 = | L(M) = Φ}
L2 = {| M on input w reaches state q in exactly 100 steps}
L3 = {| L(M) is not recursive}
L4 = {| L(M) contains at least 21 members}
 A L2 and L3 only B L1 and L3 only C L2, L3 and L4 only D L1, L3 and L4 only
Question 8 Explanation:
L1 is undecidable as emptiness problem of Turing machine is undecidable. L3 is undecidable since there is no algorithm to check whether a given TM accept recursive language. L4 is undecidable as it is similar to membership problem.
Only L3 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.
Question 8 Explanation:
L1 is undecidable as emptiness problem of Turing machine is undecidable. L3 is undecidable since there is no algorithm to check whether a given TM accept recursive language. L4 is undecidable as it is similar to membership problem.
Only L3 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.