Question

Give an example of an undecidable language B, where $B{\le }_m\overline{B}$.

Short answer

is an example of undecidable language.$B=\left\{\left(1,T\right):T\in H\right\}\cup \left\{\left(0,T\right):T\notin H\right\}$

Step-by-step solution

Undecidability

A problem is undecidable if no Turing Machine exist which will halt in finite amount of time.

Example of undecidable language

Assume H : Language of all the Turing Machine which halts on empty input. This shows H is undecidable.

Now, let us define B as:

Here, T is also a Turing Machine for some language.

If B is decidable, then a Turing Machine M for language B will show the existence of a TM M' which will decide H . Also M' with input T must run M on input (1,T) .

Also, for a TM T and $y\in \left\{0,1\right\}$we will have:

$\left(y,T\right)\in B\iff \left(1-y,T\right)\notin B\iff \left(1-y,T\right)\notin \overline{B}$

So, B reduces to $\overline{B}$and B is not decidable as H is not decidable because no Turing Machine exists M' to decide it as stated in starting of the solution.

Hence, B is undecidable but yet.