The GATE Grind

GATE 2016 CS – Question 54

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

Let $X$ be a recursive language and $Y$ be a recursively enumerable but not recursive language. Let $W$ and $Z$ be two languages such that $\overline{Y}$ reduces to $W$, and $Z$ reduces to $\overline{X}$ (reduction means the standard many-one reduction). Which one of the following statements is TRUE?

  1. $W$ can be recursively enumerable and $Z$ is recursive.
  2. $W$ can be recursive and $Z$ is recursively enumerable.
  3. $W$ is not recursively enumerable and $Z$ is recursive.
  4. $W$ is not recursively enumerable and $Z$ is not recursive.

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (C) $W$ is not recursively enumerable and $Z$ is recursive.

Explanation

$Y$ is recursively enumerable but not recursive, so its complement $\overline{Y}$ is not recursively enumerable. If $\overline{Y}$ reduces to $W$, then $W$ cannot be recursively enumerable either. Since $X$ is recursive, $\overline{X}$ is recursive, and anything that reduces to a recursive language is recursive, so $Z$ is recursive.