Question 26

Definition of Mapping Reducibility:
$A \le_m B$ means there exists a computable function $f: \Sigma^* \to \Sigma^*$ such that for all $w \in \Sigma^*$,

Properties of Mapping Reducibility:

• Decidability: If $B$ is recursive (decidable), then $A$ is recursive (decidable). To decide $w \in A$, compute $f(w)$ and run the decider for $B$. Statement (A) is TRUE.
• Undecidability: By contraposition of (A), if $A$ is undecidable, then $B$ must be undecidable. Statement (B) is TRUE.
• Recursively Enumerable (RE): If $B$ is RE, then $A$ is RE. To recognize $w \in A$, compute $f(w)$ and run the recognizer for $B$. Statement (C) is TRUE.
• Non-RE Languages: If $B$ is not RE, language $A$ can be anything simpler than $B$, including a decidable language. For instance, take $A = \emptyset$ (which is regular and decidable) and let $B = \overline{A_{TM}}$ (which is not RE). We can reduce $A \le_m B$ by fixing any string $y_0 \notin B$ and setting $f(w) = y_0$ for all $w$. Then $w \in A \iff f(w) \in B$ holds trivially ($False \iff False$). Here $B$ is not RE, but $A$ is RE (even regular). Hence, statement (D) is FALSE.