Is there an undecidable language A that is mapping reducible to its complement?

If it is possible, since A is an undecidable language, so A's complement must also be an undecidable language. But i don't know whether undecidable languages is closed under complement or not.


Yes, it is possible. Enumerate the set of all possible Turing machines and let $H$ (resp. $\overline{H}$) be the set of indices of the Turing machines that halt (resp. do not halt) on empty input.

Let $L = \{ \langle T, 1 \rangle \, : T \in H \} \cup \{ \langle T, 0 \rangle \, : T \in \overline{H} \}$.

Clearly $L$ is not decidable but it is possible to reduce $L$ to $\overline{L}$ since $\langle T, r \rangle \in L \iff \langle T, 1-r \rangle \in \overline{L}$.


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.