Consider the following statements: \(𝑆_1\): These exists no algorithm for…
2019
Consider the following statements:
\(𝑆_1\): These exists no algorithm for deciding if any two Turing machines \(𝑀_1\) and \(𝑀_2\) accept the same language
\(𝑆_2\): Let \(𝑀_1\) and \(𝑀_2\) be arbitrary Turing machines. The problem to determine \(𝐿(𝑀_1)⊆𝐿(𝑀_2)\) is undecidable
Which of the statements is (are) correct?
- A.
Only
\(𝑆_1\) - B.
Only
\(𝑆_2\) - C.
Both
\(𝑆_1\)and\(𝑆_2\) - D.
Neither
\(𝑆_1\)nor\(𝑆_2\)
Attempted by 41 students.
Show answer & explanation
Correct answer: C
Final answer: Both statements are correct — both problems are undecidable.
Statement S1: There is no algorithm to decide whether two Turing machines accept the same language (the equivalence problem). Proof sketch:
If an equivalence decider existed, we could decide the emptiness problem (whether a given Turing machine's language is empty) as follows. Given a machine M, construct a machine R that rejects every input. M and R are equivalent exactly when L(M) = ∅. Thus a decider for equivalence would decide emptiness, but emptiness is known to be undecidable. Therefore equivalence is undecidable.
Statement S2: For arbitrary Turing machines M1 and M2, deciding whether L(M1) ⊆ L(M2) is undecidable (the inclusion problem). Proof sketch:
If an inclusion decider existed, we could again decide emptiness. Given a machine M, set M1 = M and let M2 be the machine that rejects every input. Then L(M1) ⊆ L(M2) holds exactly when L(M) = ∅. This would decide emptiness, contradicting its undecidability. Hence the inclusion problem is undecidable.
Conclusion: Both statements are correct because each problem can be used to decide the (undecidable) emptiness problem, so neither admits an algorithm.