Teaching UGC NET Mock Test Series 2025 (Paper 1 & 2) Theory of Computation Recursively Enumerable Sets, Turing Machines and Undecidability Undecidability
Which of the following problems is/are decidable problem(s) (recursively enumerable) on a Turing machine M?
(a) G is a CFG with L(G) = ϕ
(b) There exist two TMs M1 and M2 such that L(M) ⊆{L(M1) U L(M2)} = language of all TMs
(c) M is a TM that accepts w using at most 2|w| cells of tape
1
(a) and (b) only
2
(a) only
3
(a), (b) and (c)
4
(c) only