Question

Which one of the following statements is equivalent to the following assertion?
Turing machine 𝑀 decides the language 𝐿⊆{0,1}∗

• A. Turing machine 𝑀 halts on all input strings in {0,1}∗
• B. Turing machine 𝑀 accepts all input strings in 𝐿
• C. Turing machine 𝑀 rejects all input strings in {0,1}∗−𝐿
• D. Turing machine 𝑀 accepts all input strings in 𝐿 and rejects all input strings in {0,1}∗−𝐿

Hint:

A Turing machine 'decides' a language only if it halts on every input and its accept or reject outcome exactly matches membership in L.

Answer 1

The Correct Option is D

Step 1: In automata theory there is a key difference between a machine that 'recognizes' or 'accepts' a language and one that 'decides' it. A recognizer accepts exactly the strings of L but may loop forever on strings outside L.
Step 2: A decider is stronger: it must halt on every input string in \(\{0,1\}^*\), giving a definite accept or reject answer, and that answer must be correct in both directions.
Step 3: Test each option against this requirement. Only accepting strings in L (without saying what happens elsewhere) does not guarantee halting on the complement. Only rejecting strings outside L (without confirming acceptance on L) does not guarantee correctness on L. Only halting everywhere does not guarantee the outcome is correct.
Step 4: The single option that forces both correct acceptance on L and correct rejection on \(\{0,1\}^* - L\) automatically forces halting everywhere too, since accept/reject are both halting outcomes, so this is the only fully equivalent statement.
Final Answer: Option (D)