# How to solve this mapping reduction problem by proving the computability of this function?

I am working on a mapping reduction problem. Define the union of two languages $L_1,L_2\subseteq\{0,1\}^*$ to be $L_1 \cup L_2 = \{x0\mid x \in L_1\} \cup \{y1\mid y \in L_2\}$. I want to prove that $L_1 \le_m L_1 \cup L_2$.

I was reading about the mapping reduction. According to mapping reductions, for any $w \in \Sigma^*$, $w \in L_1$ iff $f(w) \in L_1 \cup L_2$.

I am thinking of making my computable function $f=\{x \mid x\text{ ends with }0\}$. If I can prove that this function is computable, then I can complete my reduction. I just have two following questions:

• How to correctly prove that this $f$ is computable? I am thinking to create a TM $M$ that enumerates $w \in L_1 \cup L_2$. If the string ends with a 0, then I halt the machine and accept the result. I am not sure how to formally prove the computability of $f$.

• What do you mean by "I want to prove that L1"? In addition, {x| x ends with a} is a set, not a function. Please take some time to improve your formatting. Apr 1, 2018 at 3:50
• I guess $a$ should be 0, and $b$ should be 1 above. Otherwise, we need $\{a,b\}^*$ instead of $\{0,1\}^*$
– chi
Apr 1, 2018 at 15:24
• You probably want $f(x)=xa$ (or $x0$). Forget about enumerating sets here, you are not trying to prove that a set is r.e..
– chi
Apr 1, 2018 at 15:26
• Yeah! I apologize. 'a' should be 0 and 'b' should be 1. Let me edit it.
– WOW
Apr 1, 2018 at 19:38

$$f(x)=x0$$
which is computable, since a TM can move to the end of $x$, append a $0$, and halt. It is also total, by definition.
Note that to prove that $f$ is computable we do NOT have to consider the decidability / enumerability of any sets. I think your confusion is caused by thinking about c.e. sets when crafting $f$, but defining a reduction function does not involve enumerability. You only have to ensure that $f$ is total computable, and that $x\in A \iff f(x)\in B$ for all $x$.