Question 54

We are given:

• $X$ is a recursive language ($X \in \text{REC}$).
• $Y$ is recursively enumerable but not recursive ($Y \in \text{RE} \setminus \text{REC}$).

Properties of the languages:

1. Since $X$ is recursive and the class of recursive languages is closed under complementation, $\overline{X}$ is also recursive ($\overline{X} \in \text{REC}$).
2. For language $Y$: By Post's Theorem, a language $L$ is recursive if and only if both $L$ and $\overline{L}$ are recursively enumerable. Since $Y \in \text{RE}$ but $Y \notin \text{REC}$, its complement $\overline{Y}$ cannot be recursively enumerable ($\overline{Y} \notin \text{RE}$).

Analyzing language $Z$ ($Z \le_m \overline{X}$):

• For any many-one reduction $A \le_m B$, if $B$ is recursive, then $A$ is recursive.
• Since $\overline{X}$ is recursive, $Z$ must be recursive ($Z \in \text{REC}$).

Analyzing language $W$ ($\overline{Y} \le_m W$):

• For any many-one reduction $A \le_m B$, if $B$ is recursively enumerable, then $A$ is recursively enumerable.
• If $W$ were recursively enumerable ($W \in \text{RE}$), then $\overline{Y}$ would also be recursively enumerable.
• However, we established that $\overline{Y} \notin \text{RE}$. Therefore, $W$ cannot be recursively enumerable ($W \notin \text{RE}$).

Conclusion:
$W$ is not recursively enumerable and $Z$ is recursive. This matches option C.