Q44

MCQ2 marks, −0.67

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?

(A)

$W$ can be recursively enumerable and $Z$ is recursive.

(B)

$W$ can be recursive and $Z$ is recursively enumerable.

(C)

$W$ is not recursively enumerable and $Z$ is recursive.

(D)

$W$ is not recursively enumerable and $Z$ is not recursive.

Loading…