GATE CS 2022 Q36 — Turing Machines

To determine which of the options are undecidable, we can analyze them using Rice's Theorem and computability theory:

• Option A: Deciding if $L(M_1) = L(M_2)$ is the equivalence problem for Turing machines, which is a well-known undecidable problem.
• Option B: "$L(M)$ is regular" is a non-trivial semantic property of recursively enumerable languages. By Rice's Theorem, this property is undecidable.
• Option C: "$L(M) = \Sigma^*$" (accepts all strings) is also a non-trivial semantic property of recursively enumerable languages. By Rice's Theorem, this is undecidable.
• Option D: Deciding if $M$ takes more than $1073$ steps on every string is decidable. In $1073$ steps, a Turing machine can scan at most the first $1073$ symbols of any input string. Since the alphabet $\Sigma$ is finite, there are only finitely many input prefixes of length $\le 1073$. We can simulate $M$ on all these finite prefixes for up to $1074$ steps to determine if it ever halts in $\le 1073$ steps. Thus, this property is decidable.