Proove that Unions and intersections of recursively enumerable sets are also recursively enumerable

Question

How do I prove that Unions and intersections of recursively enumerable sets are also recursively enumerable?

Answer 1

Suppose $A, B$ are accepted by Turing machines $M_A, M_B$ respectively.

[$A\cap B$] A TM that implements the following algorithm will accept $A\cap B$:

On input $x$,

1. run $M_A$ on $x$;
2. run $M_B$ on $x$;
3. accept $x$ (halt).

If $M_A$ or $M_B$ doesn't halt on $x$, so be it: in either case, this machine won't halt either, as it will never reach the next step, so it won't accept $x$.

[$A\cup B$] A TM that implements the following algorithm will accept $A\cup B$:

On input $x$,

loop
    run $M_A$ for one more step on input $x$;
    if $M_A$ has accepted $x$, then accept $x$ (halt, return)

    run $M_B$ for one more step on input $x$;
    if $M_B$ has accepted $x$, then accept $x$ (halt, return)
end loop

The TM runs the two TMs $M_A$ and $M_B$ on $x$ "in parallel", one step at a time. If either accepts $x$, then it accepts $x$; if neither does, it will run forever.

Answer 2

I think it's more intuitive to think of a r.e. set as the ordered list of values output by a machine, rather than simply running it on a given input and asking whether it halts or not. The notions are equivalent.

Countable unions: you can construct a "volcano". Perform machine 1 for one step, then machine 2 for one step and machine 1 for one step, then machines 3,2,1 for one step, then machines 4,3,2,1 in one step, … At any point, if one of the internal machines outputs a number, get the volcano to output that number.

In this way, each internal machine gets to run for countably infinitely many time steps, so each internal machine will output anything it was ever going to output.

So the volcano outputs every number which any internal machine outputs.