[Solved]: Reducing a non-RE language to its complement

Problem Detail: 

Is there a language $L$ such that both $L$ and $L$'s complement are non turing recognizable languages, but there is a reduction between them? I couldn't find one...

Asked By : user3680924

Answered By : Tom van der Zanden

Such a undecidable language $L$ can not be in $RE$, since if there was a computable reduction from $L$ to $\overline{L}$, then $L$ would be in $R$.

Let $x'$ be the value to which $x$ reduces. $x' \in L$ if and only if $x\not \in L$. We could then decide $x\in L$ by enumerating $L$, and stopping to report that $x\in L$ as soon as we encounter $x$, and report that $x\not \in L$ when we encounter $x'$. That would make $L$ decidable, which is a contradiction. So there can be no reduction from a language in $RE$ to its complement.

By a similar argument, such a language can not be in $co-RE$ either.

There does exist an undecidable language $L$ that can be reduced to its complement. To find one, we must consider a language that is neither in $RE$ nor in $co-RE$. Let $L\in RE$ be an undecidable language. Then

$L'=\{0w|w\in L\} \cup \{1w|w\in \overline{L}\}$

is not recursive enumerable nor is its complement (see here).

But there clearly is a reduction from $L'$ to $\overline{L'}$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/37363