0
$\begingroup$

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:

  • Am I thinking correctly about this problem?

  • 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$.

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – xskxzr Apr 1 '18 at 3:50
  • $\begingroup$ I guess $a$ should be 0, and $b$ should be 1 above. Otherwise, we need $\{a,b\}^*$ instead of $\{0,1\}^*$ $\endgroup$ – chi Apr 1 '18 at 15:24
  • $\begingroup$ 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.. $\endgroup$ – chi Apr 1 '18 at 15:26
  • $\begingroup$ Yeah! I apologize. 'a' should be 0 and 'b' should be 1. Let me edit it. $\endgroup$ – WOW Apr 1 '18 at 19:38
0
$\begingroup$

The reduction function is simply

$$ 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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.