GATE 2022 CS Q.46: solution and answer

Official answer: A, B, CSource: Official answer key, GATE 2022 CS (IIT Kharagpur)

1. (A) Equivalence of two Turing machines is a property of a pair of machines, so Rice's theorem does not apply directly. Reduce from the totality problem instead: fix $M_2$ to be a machine that accepts every string, so $L(M_2)={\Sigma }^{\ast }$. Then $L(M_1)=L(M_2)$ exactly when $M_1$ accepts all strings. Totality is undecidable (see C), so equivalence is undecidable.

2. (B) "$L(M)$ is regular" is a property of the language $L(M)$. It is non-trivial: a machine for $\varnothing$ has it, and a machine for $\{a^n{b}^n\mid n\ge 0\}$ does not. By Rice's theorem it is undecidable.

3. (C) "$L(M)={\Sigma }^{\ast }$" is a property of the language $L(M)$. It is non-trivial: a machine accepting every string has it, and a machine accepting nothing does not. By Rice's theorem it is undecidable.

4. (D) This is a property of the running time, not only of the language, so Rice's theorem does not apply and we argue directly. Let $N=10^{73}$, a fixed constant. "$M$ takes more than $N$ steps on every string" means that no string makes $M$ halt within $N$ steps (a string on which $M$ loops forever counts as taking more than $N$ steps).

5. In $N$ steps the head starts at cell $0$ and can reach at most cells $0,1,\dots ,N$. So the first $N$ steps depend only on the first $N+1$ input symbols. Hence if some string $w$ makes $M$ halt within $N$ steps, then the prefix of $w$ of length at most $N+1$ (or $w$ itself if it is shorter) makes $M$ halt within $N$ steps in the same way.

6. So it is enough to simulate $M$ for $N$ steps on each of the finitely many strings over $\Sigma$ of length at most $N+1$. If any simulation halts within $N$ steps the answer is NO, otherwise YES. This is a finite, if astronomically large, computation, so (D) is decidable.

7. The undecidable problems are A, B and C.