2
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ If a problem (and its complement) is not decidable, we can not conclude that both the problem and its complement are not recognizable -- we can only conclude that (at least) one of them is not recognizable. The OP wrote it correctly in the question. Note that the claim puts the negation in the wrong place "X and Y are not Z" instead of "not (X and Y are Z)". So the first part "this claim is true" is wrong -- it would have been correct if the claim put its negation elsewhere. This is more a wording/English issue than a CS one... ;-) $\endgroup$ – chi Oct 17 '17 at 13:26
  • 1
    $\begingroup$ @chi Thanks, edited. If it were "or" instead of "&" then the claim would be true. $\endgroup$ – fade2black Oct 17 '17 at 13:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.