# A language is decidable iff it is Turing-recognizable and co-Turing-recognizable (WHY?)

I am trying to understand the proof for this theorem (theorem 4.22 of the book 'An introduction to the theory of computation'):

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


The first direction is OK. But the other is not, namely:

What I don't understand is why the author assumed that M will halt. We have that A is Turing-recognizable, and thus we are not sure we have a machine that decides it (and thus halts). Same for the complement of A which is also Turing-recognizable.

• So the trick is that a language that is recognizable has a machine that always halts on words that are in that lnguage Jan 21, 2021 at 15:47

Since both $$A$$ and $$\overline A$$ are recognizable, you know that for any input $$x$$, either
1. $$x \in A$$, which means that $$T_A$$ will halt on input $$x$$, or
2. $$x \notin A$$, which means that $$x \in \overline A$$ which means that $$T_{\overline A}$$ will halt on input $$x$$.
The "trick" here is to run $$T_A$$ and $$T_{\overline A}$$ "simultaneously", which means that if any of $$T_A$$ or $$T_{\overline A}$$ halts after $$k$$ steps, then your new machine will halt after $$2k$$ steps.
If you don't like "simultaneously", you can for each integer $$i$$ from 0 and up, run $$T_A(x)$$ for $$i$$ steps, then run $$T_{\overline A}(x)$$ for $$i$$ steps.