# 哪種不確定的語言$B$可以還原為它的補語？

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