What undecidable language $B$ is reducible to its complement?

Question

I encountered a problem which asks to give an example of an undecidable language $B$ such that $B \leq_m \overline{B}$...

However, I could find it hard to construct an example ... my difficulty is that given an undecidable but Turing recognizable language, say $A_{TM}$, its complement $\overline{A_{TM}}$ is not Turing recognizable and loops. If I reduce such a language (say $x \in A_{TM} \leq_m y \in \overline{A_{TM}}$, the instance $y \in \overline{A_{TM}}$ cannot be recognized by any TM (since by definition, $\overline{A_{TM}}$ is looping)...

Any help ?

Answer 1

Let $H$ be the language of all Turing machines that halt on empty input. Clearly $H$ is undecidable.

Let $L = \{ (1,T) : T \in H \} \cup \{ (0,T) : T \not\in H \}$.

Clearly $L$ is undecidable. If $L$ were decidable, then a Turing machine $M$ for $L$ would also imply the existence of a Turing machine $M'$ that decides $H$. $M'$ with input $T$ simply simulates $M$ with input $(1,T)$.

Moreover, for a Turing machine $T$ and $x \in \{0,1\}$ we have: $$ (x, T) \in L \iff (1-x, T) \not\in L \iff (1-x, T) \in \overline{L}. $$

This, combined with the fact that we can decide whether a given word encodes a valid Turing machine, shows that $L$ is reducible to $\overline{L}$.