GATE 2014 CS (CS1) – Question 45

Theory of Computation · Turing Machines and Undecidability · 2 marks · Multiple choice

Let L be a language and $\bar L$ its complement. Which is NOT a viable possibility?

Neither L nor $\bar L$ is recursively enumerable (r.e.).
One of L and $\bar L$ is r.e. but not recursive; the other is not r.e.
Both L and $\bar L$ are r.e. but not recursive.
Both L and $\bar L$ are recursive.

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (C) Both L and $\bar L$ are r.e. but not recursive.

Explanation

If both L and its complement are recursively enumerable, dovetail their recognisers on any input. Exactly one eventually accepts, giving a terminating decision procedure for L. Thus both must be recursive, making **C** impossible. The other listed combinations can occur.