undecidable problem and its negation is undecidable

Question

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?

Answer 1

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

Answer 2

Note that the overwhelming majority of problems fit the criterion you're looking for: both the problem and its complement are not semi-decidable. This is because there are only countably many semi-decidable problems but there are uncountably many problems.

For an example, let $H$ be the halting problem for Turing machines and let $\cal{M}$ be the class of Turing machines with an oracle for $H$. Let $H_2$ be the halting problem for $\cal{M}$. I claim that neither $H_2$ nor $\overline{H_2}$ is semi-decidable

We can show that $H_2$ is not decided by any machine in $\cal{M}$: the argument is the same as the argument that the ordinary Turing machine halting problem $H$ is not decided by any ordinary Turing machine. Now, suppose for contradiction that $H_2$ is semi-decided by some ordinary Turing machine $T$. Well, with an oracle for $H$, we can test whether $T$ halts for any particular input, contradicting the fact that no machine in $\cal{M}$ decides $H_2$. So $H_2$ is not semi-decidable.

It remains to show that $\overline{H_2}$ is not semi-decidable. First, note that it is semi-decided by a machine in $\cal{M}$: again, the argument is the same as $H$ being semi-decided by an ordinary Turing machine. $\overline{H_2}$ cannot be semi-decided by some machine in $\cal{M}$ because, if it was, $H_2$ and $\overline{H_2}$ would both be semi-decided by machines in $\cal{M}$, so both languages would be decided by machines in $\cal{M}$. But we already know that $H_2$ is not decided by any machine in $\cal{M}$. Therefore, $\overline{H_2}$ is not semi-decided by any machine in $\cal{M}$. Further, $\overline{H_2}$ is not semi-decided by any ordinary Turing machine, since $\cal{M}$ contains every ordinary Turing machine. (An ordinary Turing machine is a Turing machine with an oracle for $H$ that never uses that oracle.)

Answer 3

Here are some natural examples:

• The language of all Turing machines halting on all inputs, sometimes denoted TOT. This language is $\Pi_2^0$-complete.

• The language of all Turing machines halting on infinitely many inputs, sometimes denoted INF. This language is also $\Pi_2^0$-complete.

• The language of all Turing machines halting on arbitrarily long inputs, sometimes denoted COF. This language is $\Sigma_3^0$-complete.

$\Pi_2^0$ and $\Sigma_3^0$ are levels of the arithmetical hierarchy. The completeness results imply, in particular, that these languages are neither semidecidable nor co-semidecidable.