GATE CS Mastery
Cheat sheets

GATE CS 2013 · Theory of Computation

Question 17

MCQPrinted as CS Q.171 markWrong answer: −1/3Easy (estimate)

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 complementation.
  3. Turing decidable languages are closed under intersection and complementation.
  4. Turing recognizable languages are closed under union and intersection.
Choose one option
Official answer and solution
Official answer
C
From
Official GATE 2013 answer key

Solution

Review foundational computability theorems concerning Turing machines and closure properties of RE and Decidable languages.

Evaluate each statement:

  1. Statement 1: 'For every non-deterministic Turing machine, there exists an equivalent deterministic Turing machine.'

    • True. A standard deterministic Turing machine can simulate an NTM by performing a breadth-first search on the NTM's computation tree.

  2. Statement 2: 'Turing recognizable languages are closed under union and complementation.'

    • False. Turing recognizable (recursively enumerable) languages are closed under union and intersection, but NOT under complementation (for example, the Halting Problem is Turing-recognizable, but its complement is not).

  3. Statement 3: 'Turing decidable languages are closed under intersection and complementation.'

    • True. Decidable (recursive) languages are closed under all Boolean operations (union, intersection, complement).

  4. Statement 4: 'Turing recognizable languages are closed under union and intersection.'

    • True. We can run two Turing recognizers in parallel (time-sharing) to accept if either halts (union) or if both halt (intersection).

Therefore, only statement 2 is FALSE (Option C).

Final answer

Option (C)

Common trap

Confusing Turing-recognizable (RE, not closed under complement) with Turing-decidable (recursive, closed under complement).

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper
GATE 2013 Computer Science and Information Technology (CS)
Question
17 of 65, printed as CS Q.17
Section
Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.