GATE CS 2026 Set 2 Q3 — Turing Machines

By definition, a Turing machine $M$ decides a language $L \subseteq \Sigma^*$ if and only if it halts on all inputs $w \in \Sigma^*$ such that:

• If $w \in L$, $M$ halts and accepts $w$.
• If $w \notin L$ (i.e., $w \in \Sigma^* - L$), $M$ halts and rejects $w$.

Let us analyze the given options based on this definition for $\Sigma = \{0,1\}$:

• Option A: States only that $M$ halts on all inputs. While this is a necessary property of a decider, it does not specify which strings are accepted or rejected to define the language $L$.
• Option B: Only specifies the behavior for strings in $L$. A machine that accepts all strings in $L$ but loops infinitely on strings not in $L$ merely recognizes (semi-decides) $L$, but does not decide it.
• Option C: Only specifies the behavior for strings not in $L$.
• Option D: Correctly combines both requirements: $M$ must accept every string in $L$ and reject every string in $\{0,1\}^* - L$. This is equivalent to the assertion that $M$ decides $L$.