Which of the following statements is/are FALSE? 1. For every non-deterministic…
20132013
Which of the following statements is/are FALSE?
1. For every non-deterministic Turing machine, there exists an equivalent deterministic Turing machine.
2. Turing recognizable languages are closed under union and complementation.
3. Turing decidable languages are closed under intersection and complementation.
4. Turing recognizable languages are closed under union and intersection.
- A.
1 and 4 only
- B.
1 and 3 only
- C.
2 only
- D.
3 only
Attempted by 77 students.
Show answer & explanation
Correct answer: C
Answer: Only statement 2 is false.
Why statement 2 is false:
Turing-recognizable (recursively enumerable) languages are closed under union (simulate both recognizers in dovetailed fashion) but not necessarily closed under complementation. There exist recognizable languages whose complements are not recognizable (for example, the halting problem is recognizable but its complement is not).
Brief notes on the other statements (they are true):
For every nondeterministic Turing machine there is an equivalent deterministic Turing machine (deterministic machines can simulate nondeterministic branching).
Turing-decidable languages are closed under intersection and complementation: combine deciders or flip accept/reject to build new deciders.
Turing-recognizable languages are closed under union and intersection by dovetailing simulations of the recognizers.
A video solution is available for this question — log in and enroll to watch it.