-2
$\begingroup$

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

$\endgroup$

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
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Finite unions and intersections? Just $A\cup B$ and $A\cap B$, that is? (Effectively given countable unions are also possible). $\endgroup$ – BrianO Feb 12 '16 at 8:46
  • $\begingroup$ Yes Finite unions and intersections. $\endgroup$ – Elsban Feb 12 '16 at 8:54
  • 1
    $\begingroup$ 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? $\endgroup$ – BrianO Feb 12 '16 at 8:57
  • $\begingroup$ That is correct. A set is recursively enumerable if and only if it can be accepted by a Turing machine. $\endgroup$ – Elsban Feb 12 '16 at 9:00
  • 1
    $\begingroup$ Just to be a stickler, what does "accept" mean? Halt in an "accepting state"? or just, not run forever? $\endgroup$ – BrianO Feb 12 '16 at 9:03
2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Henning Makholm Feb 12 '16 at 10:26
  • $\begingroup$ Hah. That's embarrassing. I'll remember not to answer questions early in the morning in future. Thanks. $\endgroup$ – Patrick Stevens Feb 12 '16 at 11:04

Not the answer you're looking for? Browse other questions tagged or ask your own question.