Question

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 complemenetation
3. Turing decidable languages are closed under intersection and complemenetation
4. Turing recognizable languages are closed under union and intersection

• A. 3 only
• B. 1 and 4 only
• C. 1 and 3 only
• D. 2 only

Answer 1

The correct option is D 2 only

1. Non-deterministic Turing machine can be simulated into an equivalent deterministic Turing machine. So for every non deterministic Turing machine there exits an equivalent deterministic Turing machine. So True.
2. Turing recognizable languages (RE languages) are not closed under complementation so false.
3. Turing decidable languages (REC languages) are closed under both inter-section and complementation. So.true.
4.Turing recognizable languages (RE languages) are closed under union and intersection. So true.
So option (c) is correct.