Latest update

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

2017-10-17 12:13:55

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 \text{ is a TM and accepts } w\}$ and the other is $EQ_{TM} = \{ \ |\ 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:

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

$EQ_{TM}$ is Turing-undecidable.

Note that this reduction does not show that either of \$\overlin