Question

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

• A. Turing machine \(M\) halts on all input strings in \(\{0,1\}^*\)
• B. Turing machine \(M\) accepts all input strings in \(L\)
• C. Turing machine \(M\) rejects all input strings in \(\{0,1\}^* - L\)
• D. Turing machine \(M\) accepts all input strings in \(L\) and rejects all input strings in \(\{0,1\}^* - L\)

Hint:

Deciding a language needs BOTH correct acceptance on L and correct rejection on its complement; that combination alone forces halting everywhere too.

Answer 1

The Correct Option is D

Step 1: Split $\{0,1\}^*$, the set of all possible input strings, into exactly two disjoint pieces: $L$ itself and its complement $\{0,1\}^* - L$. Every single string in the universe falls into exactly one of these two pieces, never both and never neither.

Step 2: "Deciding" $L$ means giving a definite, halting yes or no verdict for every string in the whole universe, accept exactly for strings in $L$, and reject exactly for strings in the other piece. So a correct restatement of "decides $L$" must, between the two pieces, pin down both what happens on $L$ and what happens on its complement.

Step 3: Option (A) talks only about halting, with no mention of which strings are accepted versus rejected. A machine could halt everywhere but accept a totally unrelated language, say it accepts only even-length strings regardless of $L$, and (A) would still hold. So (A) misses the correctness half entirely.

Step 4: Option (B) only pins down the behavior on the $L$ piece, must accept, leaving the complement piece completely unconstrained, including the possibility of looping forever there. Option (C) is the mirror image, it only pins down the complement piece, must reject, leaving $L$ itself unconstrained. Each option therefore only covers one of the two pieces from Step 1, not both.

Step 5: Option (D) is the only statement that pins down both pieces at once, accept everything in $L$, reject everything in the complement. Since these two pieces exhaust $\{0,1\}^*$ with no overlap, this simultaneously guarantees $M$ halts everywhere, every string gets an explicit accept or reject verdict, and guarantees the verdict is correct everywhere, which is exactly the definition of deciding $L$.

\[ \boxed{\text{Option D}} \]