5
$\begingroup$

I'm reading "Theory of Computation" by Michael Sipser and I've encountered a solution (provided by the book) that I don't understand.

The question:

Show that the collection of Turing-recognizable languages is closed under the operation of union.

The answer:

For any two Turing-Recognizable languages $L_1$ and $L_2$, let $M_1$ and $M_2$ be the $\textsf{TM}$s that recognize them. We construct a $\textsf{TM}$ $M'$ that recognize the union of $L_1$ and $L_2$:

On input $w$:

  1. Run $M_1$ and $M_2$ alternately on $w$ step by step. If either accpts, $accept$. If both half and reject, $reject$.

If either $M_1$ or $M_2$ accepts $w$, $M'$ accepts $w$ because the accepting $\textsf{TM}$ arrives to its accepting state after a finite number of steps. Note that if both $M_1$ and $M_2$ reject and either of them does so by looping, then $m'$ will loop.

Why does alternating Turing machines work for checking union? That sounds like a good approach for perfect shuffle, but not unions.

I'm also not sure why the book's answer for the same question for decidable languages (below) is not sufficient.

On input $w$:

  1. Run $M_1$ on $w$. If it accepts, $accept$.
  2. Run $M_2$ on $w$. If it accepts, $accept$. Otherwise, $reject$.

The difference between Turing-recognizable and decidable, as far as I can tell, is that deciders always halt.

$\endgroup$
1
  • 7
    $\begingroup$ You need to make sure that if either machine halts that the union machine halts. If you sequentialise, this may never happen. It's like alternatively checking two fishing lines :-). $\endgroup$ Commented Mar 6, 2015 at 0:52

1 Answer 1

Reset to default
3
$\begingroup$

I believe it's called the technique of interleaving or dovetailing. Since running a TM on a given input may never halt, there may not be an opportunity to run the second machine at all. Thus the approach may not "recognize" the union language.

So, we run machine

M1 on input w for step 1

then run M1 on input w for step 2 and Run M2 on input w for step1

...

..

. This way, we get an opportunity to check whether either machine accepts and thus build the "recognizer"

$\endgroup$

You must log in to answer this question.