GATE 2026 CS2 Q.13: solution and answer

Official answer: DSource: Official answer key, GATE 2026 CS2 (IIT Guwahati)

1. A Turing machine $M$ decides $L\subseteq \{0,1{\}}^{\ast }$ if it halts on every input $w\in \{0,1{\}}^{\ast }$, accepting when $w\in L$ and rejecting when $w\notin L$.

2. Check (A): halting on all inputs is necessary but not sufficient. A machine that halts everywhere but accepts the wrong strings decides some other language, not $L$.

3. Check (B): accepting every string of $L$ only gives $L\subseteq L(M)$. $M$ may also accept strings outside $L$, or loop on them. This is at best a recognising condition.

4. Check (C): rejecting every string of $\{0,1{\}}^{\ast }-L$ says nothing about strings in $L$. $M$ could reject them or loop on them.

5. Check (D): $M$ accepts every string of $L$ and rejects every string of $\{0,1{\}}^{\ast }-L$. Every input in $\{0,1{\}}^{\ast }$ lies in $L$ or in its complement, so every input gets a definite accept or reject. Hence $M$ halts on all inputs and $L(M)=L$, which is exactly the definition of deciding $L$.

6. Rejecting a string means halting in the reject state. So (D) already contains both halting on all inputs and correct classification of every string. Only (D) is equivalent to the assertion.