# Find an undecidable language that is mapping-reducible to its complement

As the title suggests. Also, such a language must satisfy that neither it nor its complement are semi-decidable. I already know that $All_{TM}, EQ_{TM}, T$ (that is the set of all deciders) satisfy this property. But I tried reducing these to their complements directly, and via some sort of intermediate language, but to no avail. Can anyone help?

-

Try the following construction. Given a language $L$, use $$\{0x : x \notin L\} \cup \{1x : x \in L\}.$$

-
I'm not quite sure what you mean. Can you perhaps expand a little bit on this? –  Aden Dong Oct 17 '12 at 2:42
Consider all possible words. Prefix those which belong to $L$ by $1$, those that don't by $0$. This may be relevant to your question. –  Yuval Filmus Oct 17 '12 at 4:52
Question: is the sentence true (in the standard model $\mathbb{N}$)?