Project ForgeWhich 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.
- A1 and 4 only
- B1 and 3 only
- 2 only
- D3 only
Explanation
1 is TRUE (NTMs and DTMs are equally powerful — every NTM has an equivalent DTM). 2 is FALSE: RE (Turing-recognizable) languages ARE closed under union, but are NOT closed under complementation in general. 3 is TRUE: decidable languages are closed under both intersection and complementation. 4 is TRUE: RE languages are closed under both union and intersection. So only statement 2 is false.
Source: GATE CS 2013 (2013)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.