-2

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

Asaf Karagila
  • 393,674
Elsban
  • 113
  • Finite unions and intersections? Just $A\cup B$ and $A\cap B$, that is? (Effectively given countable unions are also possible). – BrianO Feb 12 '16 at 08:46
  • Yes Finite unions and intersections. – Elsban Feb 12 '16 at 08:54
  • 1
    What's your working definition of r.e.? A set $X$ is r.e. iff there's some Turing machine $M$ such that $X = {x\in\Bbb N\mid M\downarrow x}$ ? (where $M\downarrow x$ means "$M$ halts on input $x$") Or something different? – BrianO Feb 12 '16 at 08:57
  • That is correct. A set is recursively enumerable if and only if it can be accepted by a Turing machine. – Elsban Feb 12 '16 at 09:00
  • 1
    Just to be a stickler, what does "accept" mean? Halt in an "accepting state"? or just, not run forever? – BrianO Feb 12 '16 at 09:03
  • Accept means it will halt – Elsban Feb 12 '16 at 09:15
  • Ah, then I'm ok with my answer :) Sometimes the exact definition varies in a detail or two which would affect the descriptions of the TMs for $\cap$ and $\cup$. – BrianO Feb 12 '16 at 09:17

2 Answers2

4

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.

BrianO
  • 16,579
0

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.

Patrick Stevens
  • 36,135
  • 1
    Countable intersections of r.e. languages are not necessarily r.e. For example the set of "all Turing machines that never halt (on the empty tape)" is the intersection of "all machines that run for at least $n$ steps" (which is even computable). But the non-halting machines cannot be r.e. because that would make the halting problem decidable. – hmakholm left over Monica Feb 12 '16 at 10:26
  • Hah. That's embarrassing. I'll remember not to answer questions early in the morning in future. Thanks. – Patrick Stevens Feb 12 '16 at 11:04