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
0 comments:
Post a Comment
Let us know your responses and feedback