How do I prove that Unions and intersections of recursively enumerable sets are also recursively enumerable?
closed as off-topic by Carl Mummert, N. F. Taussig, Daniel W. Farlow, Kamil Jarosz, Pragabhava Feb 12 '16 at 14:44
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Carl Mummert, N. F. Taussig, Daniel W. Farlow, Kamil Jarosz, Pragabhava
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$,
- run $M_A$ on $x$;
- run $M_B$ on $x$;
- 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.
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.