= Solution
A <recursive set> $E\subseteq\mathbb N_0$ has an <indicator function> computed by a <register machine> that halts on every input. A <recursively enumerable set> is the exact halting set of some register machine; equivalently, it is the domain of a <partial computable function>.
If $E$ is recursive, its decider immediately gives machines that halt exactly on $E$ and on $\mathbb N_0\setminus E$, so both sets are recursively enumerable. Conversely, suppose machines $M_E$ and $M_{E^c}$ recognize the two sets. On input $x$, use <dovetailing> to run one step of $M_E(x)$ and one step of $M_{E^c}(x)$ alternately. Exactly one must eventually halt. Return one if $M_E$ halts first and zero if $M_{E^c}$ halts first. This is a total decider for $E$, so $E$ is recursive.
Back to article page
