Reduction function from A to its complement

Question

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!

Answer 1

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