Gate CS-2013 Question Paper With Solutions

Q. 17 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

Answer: (C)

Explanation: