GATE CS 2014 Set 2 Q16 — Undecidability

Mapping reducibility ($A \leq_m B$) means there exists a computable function $f: \Sigma^* \to \Sigma^*$ such that for every string $w$:

This reduction implies that $A$ is at most as hard as $B$. We can analyze each option based on this property:

• Option A: If $B$ is recursive (decidable), we can decide $A$ by first computing $f(w)$ and then running the decider for $B$ on $f(w)$. Thus, $A$ is recursive. This statement is TRUE.
• Option B: This is the contrapositive of Option A. If $A$ is undecidable, then $B$ must also be undecidable (otherwise, if $B$ were decidable, $A$ would be decidable too). This statement is TRUE.
• Option C: If $B$ is recursively enumerable (RE), we can semi-decide $A$ by computing $f(w)$ and running the semi-decider for $B$ on $f(w)$. Thus, $A$ is RE. This statement is TRUE.
• Option D: The contrapositive of Option C is: "If $A$ is not RE, then $B$ is not RE". Option D incorrectly states the converse: "If $B$ is not RE, then $A$ is not RE".

Counterexample for D:

Let $A = \emptyset$ (which is recursive, and therefore RE) and $B = \overline{HP}$ (the complement of the Halting Problem, which is not RE). We can easily map any string $w \in A$ to a string $f(w) \notin B$ because $A$ is empty. Thus, $A \leq_m B$ holds, but $A$ is RE while $B$ is not RE. Hence, Option D is FALSE.