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

Improve this question
$\endgroup$
4
  • 3
    $\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
    Commented Apr 1, 2018 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
    Commented Apr 1, 2018 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
    Commented Apr 1, 2018 at 15:26
  • $\begingroup$ Yeah! I apologize. 'a' should be 0 and 'b' should be 1. Let me edit it. $\endgroup$
    – WOW
    Commented Apr 1, 2018 at 19:38

1 Answer 1

Reset to default
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$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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