Does showing a problem and its complement are not Turing-decidable means that the language & its complement are not Turing-recognizable?

Question

I was reading the Sipser's book on the Theory of Computation, 3rd edition and came up with a question. "Does showing a problem and its complement are not Turing-decidable means that the language & its complement are not Turing-recognizable?" I believe that the answer is NO, however, the Theorem 5.30 states something different.

There are two problems concerned in this question. One is $A_{TM} = \{ <M,w>\ |\ M \text{ is a TM and accepts } w\}$ and the other is $EQ_{TM} = \{ <M_1,M_2>\ |\ M_1, M_2 \text{ are a TMs and } L(M_1) = L(M_2)\}$.

On Page 238, the Theorem 5.30 is stated as follows:

Theorem 5.30 $EQ_{TM}$ is neither Turing-recognizable nor co-Turing-recognizable.

The proof is by mapping reduction of $A_{TM}$ to $\overline{EQ_{TM}}$, and at the same time, reduction from $A_{TM}$ to $EQ_{TM}$. This way, it has shown:

1. $\overline{EQ_{TM}}$ is Turing-undecidable.
2. $EQ_{TM}$ is Turing-undecidable.

Note that this reduction does not show that either of $\overline{EQ_{TM}}$ or $EQ_{TM}$ are not Turing-recognizable, since $A_{TM}$ is Turing-recognizable.

On the other hand, on Page 209, we have the following definition

A language is co-Turing-recognizable if it is the complement of a Turing-recognizable language.

which is accompanied by Theorem 4.22:

Theorem 4.22 A language is decidable iff it is Turing-recognizable and co-Turing Recognizable.

Therefore, we can obtain the following Corollary: If a language is not decidable, then either the language itself, its complement or both of them are not Turing-recognizable.

Therefore, it is shown on Theorem 5.30 that $\overline{EQ_{TM}}$ and $EQ_{TM}$ are Turing-undecidable. This does not tell me anything more than the following proposition:

Either $EQ_{TM}$ or $\overline{EQ_{TM}}$ or both are not Turing-recognizable.

However, the Theorem 5.30 states something stronger.

Am I missing something?

Answer 1

... a problem and its complement are not Turing-decidable means that the language & its complement are not Turing-recognizable?

This claim is false. In fact, at least one of them (or both are) is Turing-recognizable. Assume that both the set (problem) $A$ and its complement $\overline{A}$ are not decidable. Then if both $A$ and $\overline{A}$ were recognizable (recursively enumerable) then that would mean $A$ and hence $\overline{A}$ are decidable (Theorem 4.22), a contradiction.

... however, the Theorem 5.30 states something different.

This theorem states that $EQ_{TM}$ is neither Turing-recognizable nor co-Turing-recognizable. In other words, both $EQ_{TM}$ and $\overline{EQ}_{TM}$ are not Turing-recognizable (recursively enumerable). This does not contradict to the above-stated claim.

Also, pay attention that the theorem 5.30 reduces $A_{TM}$ to $\overline{EQ}_{TM}$ (not to $EQ_{TM}$ as you claim in your post) meaning that $EQ_{TM}$ cannot be Turing-recognizable (otherwise $\overline{A}_{TM}$ would be Turing-recognizable and hence decidable).

You are right, if a language is not decidable, then either the language itself, its complement or both of them are not Turing-recognizable, and since the theorem 5.30 proves that $EQ_{TM}$ is not decidable, it follows that either $EQ_{TM}$ either, $\overline{EQ}_{TM}$ or both of them are not Turing-recognizable. But this result is weaker and does not contradict to the theorem 5.30. In fact the latter (weaker) result is not necessary since the theorem already establishes the stronger result.

Answer 2

It is easy to see that if both $L$ and it's complement $\bar{L}$ are recognizable by Turing machine, they can be decided (copy the input to a new tape, then run the machines for $L$ and $\bar{L}$ in parallel, the first one to stop tells you what the answer is; by assumption at least one of them stops in finite time). So the possibilities are:

• $L$ and $\bar{L}$ are both decidable
• $L$ is recognizable but not decidable, then $\bar{L}$ is not recognizable.
• None of $L$ and $\bar{L}$ are recognizable.

Check out Rice's theorem, it's proof is quite approachable. And it supplies examples of the third case above. For instance, let $L = \{M \colon \mathcal{L}(M) \text{ is regular}\}$, so that $\bar{L} = \{M \colon \mathcal{L}(M) \text{ is not regular}\}$. But both properties are non-trivial, thus non-decidable.