What undecidable language $B$ is reducible to its complement? 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 ?
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}$.