1
$\begingroup$

In undergrad theory classes, the idea of decidability and recognizability is introduced. It's well known that $A_{TM}$, the set of words accepted by a TM $M$, is recognizable but not decidable. We also know that the complement problem $\overline{A}_{TM}$ is co-recognizable but not recognizable.

I have a doubt about the co-recognizability part. If $\overline{A}_{TM}$ is co-recognizable, then we have a TM that recognizes the set of words not accepted by some TM $M$. Doesn't that mean $\overline{A}_{TM}$ is recognizable, since we have a machine that recognizes the language?

I know this can't be the case, but I'm not able to find out where I'm going wrong with my logic.

$\endgroup$
1
$\begingroup$

This statement is incorrect.

If $\overline{A_{TM}}$ is co-recognizable, then we have a TM that recognizes the set of words not accepted by some TM $M$.

The fact that $\overline{A_{TM}}$ is co-recognizable means that there is a TM $T$ that recognizes all words not in $\overline{A_{TM}}$. Equivalently, $T$ recognizes all words in $\overline{\overline{A_{TM}}}=A_{TM}$, i.e., $T$ recognizes all words accepted by $M$.

$\endgroup$
0

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.