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

Question

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.

Thanks in advance

Answer 1

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.

The latter is simpler to "program" on a single-taped Turing machine, but the former is quite okay to implement on a two-taped Turing machine.