Which one of the following statements is equivalent to the following…
2026
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}∗ − L
- D.
Turing machine 𝑀 accepts all input strings in 𝐿 and rejects all input strings in {0,1}∗ − L
Attempted by 43 students.
Show answer & explanation
Correct answer: D
A Turing machine M decides a language L if and only if it halts on all inputs.
Specifically, for every input string w in the alphabet, M must halt and either accept or reject.
If w is in L, M must accept. If w is not in L, M must reject.
Option D captures both conditions: acceptance for strings in L and rejection for strings outside L.