# Reduction function from A to its complement

I wanted to ask a simple question.

Lets say we have A, language of all the words with more then 3 letters. so it belongs to R.

and its complement , is the language of all words with less then 3 letters.

is it possible to say that I can define a turing reduction between them?

i thought about something like this: $$f(x) = \begin{cases} 01 & \text{if }x \in A, \\ 1234 & \text{ } else.\end{cases}$$

my friend is saying this solution is not good since, the definition is: $\qquad\displaystyle x \in L_2 \iff f(x) \in L_1$

and what i got is

$\qquad\displaystyle x \notin L_2 \iff f(x) \in L_1$

If in this case it wont work can you explain me why? Thank you!

• Do you want to prove that $A \leq_T \overline{A}$ and $\overline{A} \leq_T A$ assuming $A = \{w : |w| > 3\}$? Dec 24 '17 at 19:10
• yes, that is exactly what i want to prove @fade2black Dec 24 '17 at 19:28

This is true for any recursive language $A$ different from $\emptyset$ and $\Sigma^*$ for some finite alphabet $\Sigma$. Your definition is correct. In general you could define $f$ as following. Let $a\in A$ and $\overline{a} \in \overline{A}$.
$$f(x)= \begin{cases} \overline{a} & x\in A \\ a & x\notin A \end{cases}$$ From this definition it follows $x \in A \iff f(x) \in \overline{A}$. Moreover, since $A$ is recursive $f$ is computable for any $x$ and hence $A \leq_T \overline{A}$.
The whole point is to decide $x \in A$ by using $f(x)$ and $\overline{A}$. So, given $x$ you can effectively say whether or not $x \in A$ only by looking at if $f(x) \in \overline{A}$. If $f(x) =\overline{a} \in \overline{A}$ then $x$ is in $A$, otherwise $x$ is not in $A$. Hence $A \leq_T \overline{A}$.
• I must ask, why my definition of f does not define reduction between them? after all in the first case my $a$=1234 and its complement equal 01, is'nt that supposed to be the same? Dec 24 '17 at 19:36