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

| cite | improve this answer | |

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.