The GATE Grind

GATE 2026 CS (CS2) – Question 13

Theory of Computation · Turing Machines and Undecidability · 1 mark · Multiple choice

Which one of the following statements is equivalent to the assertion: Turing machine $M$ decides the language $L \subseteq \{0,1\}^{*}$?

  1. Turing machine $M$ halts on all input strings in $\{0,1\}^{*}$.
  2. Turing machine $M$ accepts all input strings in $L$.
  3. Turing machine $M$ rejects all input strings in $\{0,1\}^{*} - L$.
  4. Turing machine $M$ accepts all input strings in $L$ and rejects all input strings in $\{0,1\}^{*} - L$.

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (D) Turing machine $M$ accepts all input strings in $L$ and rejects all input strings in $\{0,1\}^{*} - L$.

Explanation

A Turing machine decides a language if it halts on every input and accepts exactly the strings in the language while rejecting all strings not in the language. Options (A), (B), and (C) each capture only part of that definition. Option (D) states both acceptance of all strings in $L$ and rejection of all strings in $\{0,1\}^{*}-L$, which is equivalent to deciding $L$. Therefore, option (D) is correct.