UGC NET CSE | December 2019 | Part 2 | Question: 51

Question

Consider the following statements:

$S_1$: These exists no algorithm for deciding if any two Turing machines $M_1$ and $M_2$ accept the same language

$S_2$: Let $M_1$ and $M_2$ be arbitrary Turing machines. The problem to determine $L(M_1) \subseteq L(M_2)$ is undecidable 

Which of the statements is (are) correct?

• A. Only $S_1$
• B. Only $S_2$
• C. Both $S_1$ and $S_2$
• D. Neither $S_1$ nor $S_2$

Answer 1

Option C is the answer. Both S1 and S2 are correct.