For a statement A language \(𝐿⊆Σ^∗\) is recursive if there exists some turing…
2019
For a statement
A language \(𝐿⊆Σ^∗\) is recursive if there exists some turing machine \(𝑀\). Which of the following conditions is satisfied for any string \(𝜔\)?
- A.
If
\(𝜔∈𝐿\), then\(𝑀\)accepts\(𝜔\)and\(𝑀\)will not halt - B.
If
\(𝜔∉𝐿\), then\(𝑀\)accepts\(𝜔\)and\(𝑀\)will halt by reaching at final state - C.
If
\(𝜔∉𝐿\), then\(𝑀\)halts without reaching to acceptable state - D.
If
\(ω∈L,\), then\(𝑀\)halts without reaching to an acceptable state
Attempted by 53 students.
Show answer & explanation
Correct answer: C
Definition: A language L ⊆ Σ* is recursive (decidable) if there exists a Turing machine M that halts on every input.
For any string ω ∈ L: M halts and accepts ω.
For any string ω ∉ L: M halts and rejects ω (i.e., halts without accepting).
Therefore the correct condition is: for inputs not in the language, the machine halts without reaching an accepting state. Other presented statements are incorrect because they either contradict halting behavior or claim the machine accepts inputs outside the language.
A video solution is available for this question — log in and enroll to watch it.