GATE CS 2026 Set 2 Q.13: Decidability, Reducibility and Undecidability

Which one of the following statements is equivalent to the following assertion?

Turing machine $M$ decides the language $L \subseteq \{0,1\}^*$

Turing machine $M$ halts on all input strings in $\{0,1\}^*$

Turing machine $M$ accepts all input strings in $L$

Turing machine $M$ rejects all input strings in $\{0,1\}^* - L$

Turing machine $M$ accepts all input strings in $L$ and rejects all input strings in $\{0,1\}^* - L$

Official answer and solution

Official answer: D
From: Official GATE 2026 answer key

Solution

Recall the definition of a Turing machine deciding a language $L$ : it must halt and accept every string in $L$ , and halt and reject every string not in $L$ .

For a Turing machine $M$ to decide a specific language $L \subseteq \{0,1\}^*$ , $M$ must be a total Turing machine whose accepted language is $L$ : specifically, $M$ must halt and accept every $w \in L$ , and halt and reject every $w \in \{0,1\}^* - L$ . Option (A) only says $M$ halts on all inputs without tying $M$ to $L$ ; Options (B) and (C) each state only one half of the condition.

Final answer

Option (D)

Common trap

Selecting (A), which states that $M$ is a decider for some language, not necessarily $L$ .

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2026 Computer Science and Information Technology - Session 2 (CS2)
Question: 13 of 65
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source