UGC NET Computer Science December 2019 | Question 101

Question 101

---

Consider the following statements :
S₁: These exists no algorithm for deciding if any two Turing machines M₁ and M₂ accept the same language.
S₂: Let M₁ and M₂ be arbitrary Turing machines. The problem to determine L(M₁) ⊆ L(M₂) is undecidable.
Which of the statements is (are) correct?

1. 1. Only S₁
2. 2. Only S₂
3. 3. Both S₁ and S₂
4. 4. Neither S₁ nor S₂

Answer : 3. Both S₁ and S₂

Question 102 Explanation

S₁ : "There exists no algorithm for deciding if any two Turing machine M1 and M2 accept the same language."
Statement S₁ is correct because "Equivalence problem of recursively enumerable languages is undecidable.
Hence, No Algorithm possible.

S₂ : "The problem of determining wether a Turing machine halts on any input is undecidable."
Statement S₂ is correct because subset problem of recursively enumerable languages is undecidable. It is the standard "Halting problem of TM". Hence, No Algorithm possible.

So, option 3 is correct answer

Previous	Next
UGC NET CS December 2019 - Question 100	UGC NET CS December 2019 - Question 102