2
$\begingroup$

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

$\endgroup$

1 Answer 1

5
$\begingroup$

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

$\endgroup$
1
  • $\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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.