Teaching UGC NET Mock Test Series 2025 (Paper 1 & 2) Theory of Computation Recursively Enumerable Sets, Turing Machines and Undecidability Undecidability
Consider the following statements():
S1: There exists no algorithm for deciding if any two Turing machines M1 and M2 accept
the same language.
S2: The problem of determining whether a Turing machine halts on any input is undecidable.
Which of the following options is correct?1
Both S1 and S2 are correct
2
Both S1 and S2 are not correct
3
Only S1 is correct
4
Only S2 is correct