Theory-of-Computation
October 6, 2023UGC NET Dec-2020 and June-2021 Paper-2
October 6, 2023Theory-of-Computation
| 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}
| L2 and L3 only
| |
| L1 and L3 only
| |
| L2, L3 and L4 only | |
| 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.
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.
Correct Answer: D
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.
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.
Subscribe
Login
0 Comments