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!

  • $\begingroup$ Do you want to prove that $A \leq_T \overline{A}$ and $\overline{A} \leq_T A$ assuming $A = \{w : |w| > 3\}$? $\endgroup$ – fade2black Dec 24 '17 at 19:10
  • $\begingroup$ yes, that is exactly what i want to prove @fade2black $\endgroup$ – secret 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}$.

  • $\begingroup$ 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? $\endgroup$ – secret Dec 24 '17 at 19:36
  • $\begingroup$ I edited. Your def is correct. $\endgroup$ – fade2black Dec 24 '17 at 19:37

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.