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...
1 Answer
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'}$.
-
$\begingroup$ It looks like I misread the question. By virtue of good luck I did end up answering the question, and provided a bonus proof in the process. $\endgroup$ Jan 18, 2015 at 22:52