Question 46

Evaluating each problem:

• (A) UNDECIDABLE: Deciding whether two arbitrary Turing machines accept the same language ($L(M_1) = L(M_2)$) is the equivalence problem for TMs, which is undecidable.
• (B) UNDECIDABLE: By Rice's theorem, any non-trivial semantic property of the language recognized by a Turing machine is undecidable. Regularity of $L(M)$ is non-trivial (some TMs accept regular languages, while others do not), so it is undecidable.
• (C) UNDECIDABLE: Deciding whether a TM accepts all strings ($L(M) = \Sigma^*$) is the universality problem, which is another non-trivial semantic property and hence undecidable by Rice's theorem.
• (D) DECIDABLE: If a TM takes more than $10^{73}$ steps on every string, it implies that on any string of length greater than $10^{73}$, the input reading alone cannot finish within $10^{73}$ steps. Moreover, the number of distinct configurations of $M$ reachable in $10^{73}$ steps on strings of length up to $10^{73}$ is finite. Since only a bounded number of execution steps are checked across a finite set of initial tape prefixes, this property can be decided by systematic simulation. Hence (D) is decidable.

Thus, problems (A), (B), and (C) are undecidable.