[Solved]: undecidable problem and its negation is undecidable

Problem Detail: 

A lot of "famous" undecidable problems are nonetheless at least semidecidable, with their complement being undecidable. One example above all can be the halting problem and its complement.

However, can anybody give me an example in which both a problem and its complement are undecidable and not semidecidable? I thought about the diagonalization language Ld, but it does not seem to me that the complement is undecidable.

In that case, does that mean that a Turing Machine M can "lose" some strings that instead should be recognized, since they're part of the language we're trying to indentify?

Asked By : Giulia Frascaria

Answered By : D.W.

Consider the following language:

$$L_2 = \{(M_1,x_1,M_2,x_2) : \text{$M_1$ halts on input $x_1$ and $M_2$ doesn't halt on input $x_2$}\}.$$

$L_2$ is undecidable and not semi-decidable, and same is true of its complement. Why? The intuition is "$M_2$ doesn't halt on input $x_2$" isn't semi-decidable, so $L_2$ is not semi-decidable; and when you look at the complement of $L_2$, the same thing happens for $M_1$. This can be formalized more carefully using reductions.

More generally, if $L$ is a language that is undecidable and not semi-decidable, then

$$L' = \{(x,y) : x \in L, y \notin L\}$$

meets your requirements: $L'$ is undecidable and not semi-decidable, and the same is true of the complement of $L'$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/45826