Teaching UGC NET Mock Test Series 2025 (Paper 1 & 2) Theory of Computation Recursively Enumerable Sets, Turing Machines and Undecidability Undecidability
Consider the following problems:
(i) Whether a finite automaton halts on all inputs?
(ii) Whether a given Context Free Language is Regular?
(iii) Whether a Turing Machine computes the product of two numbers?
Which one of the following is correct?1
Only (ii) and (iii) are undecidable problems
2
(i), (ii) and (iii) are undecidable problems
3
Only (i) and (ii) are undecidable problems
4
Only (i) and (iii) are undecidable problems