GATE CS 2016 Set 1 Q44 — Undecidability

To determine the properties of the languages $W$ and $Z$, we use the standard closure properties of many-one reductions ($\\le_m$):

1. If $A \le_m B$ and $B$ is Recursive (REC), then $A$ is Recursive (REC).
2. If $A \le_m B$ and $B$ is Recursively Enumerable (RE), then $A$ is Recursively Enumerable (RE).
3. If $L$ is REC, then its complement $\overline{L}$ is also REC.
4. If $L$ is RE but not REC, then its complement $\overline{L}$ is not RE.

Step 1: Analyze Language $Z$

• We are given that $X$ is recursive (REC).
• Therefore, its complement $\overline{X}$ is also recursive (REC).
• We are given $Z \le_m \overline{X}$.
• Since $\overline{X}$ is recursive, any language that reduces to it must also be recursive. Thus, $Z$ is recursive.

Step 2: Analyze Language $W$

• We are given that $Y$ is RE but not recursive.
• Therefore, its complement $\overline{Y}$ is not RE (it is co-RE but not RE).
• We are given $\overline{Y} \le_m W$.
• By contrapositive of property (2), if $W$ were RE, then $\overline{Y}$ would also have to be RE. Since $\overline{Y}$ is not RE, $W$ cannot be RE (i.e., $W$ is not recursively enumerable).

Conclusion

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

This matches Option C.