Question

Which of the following is/are undecidable?

• A. Given two Turing machines \( M_1 \) and \( M_2 \), decide if \( L(M_1) = L(M_2) \).
• B. Given a Turing machine \( M \), decide if \( L(M) \) is regular.
• C. Given a Turing machine \( M \), decide if \( M \) accepts all strings.
• D. Given a Turing machine \( M \), decide if \( M \) takes more than 1073 steps on every string.

Hint:

Many problems related to Turing machines, such as language equivalence and language regularity, are undecidable.

Answer 1

The Correct Option is A, B, C

(A) Undecidable. The problem of deciding whether two Turing machines accept the same language is undecidable because it is equivalent to the language equivalence problem, which is undecidable.

(B) Undecidable. Deciding if a Turing machine's language is regular is undecidable, as it is related to the regularity problem for Turing machines, which is undecidable.

(C) Undecidable. The problem of deciding whether a Turing machine accepts all strings is undecidable and is related to the halting problem, which is undecidable.

(D) Decidable. The problem of determining whether a Turing machine takes more than a fixed number of steps on every string is decidable, as it can be determined in a finite number of steps.