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:

enter image description here

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

  • $\begingroup$ So the trick is that a language that is recognizable has a machine that always halts on words that are in that lnguage $\endgroup$ – younes zeboudj Jan 21 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.

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.


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.