Which statement is equivalent to: Turing machine M decides language L ⊆ {0,1}*
2026
Which statement is equivalent to:
Turing machine M decides language L ⊆ {0,1}*
- A.
Turing machine 𝑀 halts on all input strings in {0,1}∗
- B.
Turing machine 𝑀 accepts all input strings in L
- 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} ∗ − 𝐿
Attempted by 35 students.
Show answer & explanation
Correct answer: D
A Turing machine M decides a language L if it satisfies two main conditions for every input string w.
First, M must halt on all inputs, meaning it never enters an infinite loop.
Second, M must accept w if w is in L, and reject w if w is not in L.
This combination ensures that for any input, the machine provides a definitive decision (accept or reject) in finite time.
A video solution is available for this question — log in and enroll to watch it.