1
$\begingroup$

One of my friend told me that there is a language $C$ for every two languages $A$ and $B$ s.t $A \leq_{m} C$ and $B \leq_{m} C$ , he simply define two languages $A’=\{0w|w \in A\}$ and $B’=\{1w|w \in B\}$ so $C=A’ \cup B’$ and he define the function $f(w)=0w$ if $w \in A$ and and $f(w)=1w$ otherwise. I suspect this function is turing-computable. Suppose $A$ be $\overline{HP}$ which is not RE. How we can decide if $w \in A$ ? Even i ask myself can we realy prove that such a mapp-reduction always exist ?

$\endgroup$
2
  • $\begingroup$ The reduction always exists – you just defined it. $\endgroup$ May 18 at 21:52
  • $\begingroup$ @YuvalFilmus But how f(w) decide that is w member of A or not ? Is that computable to check membership of w in arbitary language A ? $\endgroup$ May 18 at 21:55
1
$\begingroup$

The definition of the reduction is wrong.

We actually need to define two reductions: from $A$ to $C$ and from $B$ to $C$. The reduction from $A$ to $C$ maps $w$ to $0w$. The reduction from $B$ to $C$ maps $w$ to $1w$.

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