[proofplan] We prove both implications by converting between deciders and recognizers. If $A$ is computable, then a decider for the characteristic function $\mathbb{1}_A$ immediately gives recognizers for $A$ and for its complement by halting only on the appropriate answer. Conversely, if $A$ and its complement are computably enumerable, then on input $n$ we run the two recognizers in dovetailing fashion; since every $n \in \mathbb{N}$ lies in exactly one of $A$ and $\mathbb{N} \setminus A$, exactly one recognizer has a reason to halt, and that halt determines the value of $\mathbb{1}_A(n)$. [/proofplan] [step:Construct recognizers from a decider for $A$] Assume that $A$ is [computable](/page/Computable%20Set). By definition, there exists a Turing machine $D$ computing the total [characteristic function](/page/Characteristic%20Function) \begin{align*} \mathbb{1}_A: \mathbb{N} &\to \{0,1\}. \end{align*} Thus, for every input $n \in \mathbb{N}$, the computation $D(n)$ halts and outputs $\mathbb{1}_A(n)$. Define a Turing machine $M_1$ as follows. On input $n \in \mathbb{N}$, run $D(n)$. If $D(n)$ outputs $1$, then halt and accept. If $D(n)$ outputs $0$, then enter an infinite loop. Since $D$ halts on every input, $M_1$ halts exactly on those $n$ satisfying $\mathbb{1}_A(n)=1$, equivalently exactly on $A$. Hence $A$ is [computably enumerable](/page/Computably%20Enumerable%20Set). Define a Turing machine $M_0$ as follows. On input $n \in \mathbb{N}$, run $D(n)$. If $D(n)$ outputs $0$, then halt and accept. If $D(n)$ outputs $1$, then enter an infinite loop. Again $D$ halts on every input, and $M_0$ halts exactly on those $n$ satisfying $\mathbb{1}_A(n)=0$, equivalently exactly on $\mathbb{N} \setminus A$. Hence $\mathbb{N} \setminus A$ is [computably enumerable](/page/Computably%20Enumerable%20Set). [/step] [step:Dovetail the two recognizers to decide membership in $A$] Assume that $A$ and $\mathbb{N} \setminus A$ are [computably enumerable](/page/Computably%20Enumerable%20Set). Let $M_1$ be a Turing machine recognizing $A$, meaning that for every $n \in \mathbb{N}$, the computation $M_1(n)$ halts if and only if $n \in A$. Let $M_0$ be a Turing machine recognizing $\mathbb{N} \setminus A$, meaning that for every $n \in \mathbb{N}$, the computation $M_0(n)$ halts if and only if $n \in \mathbb{N} \setminus A$. Define a Turing machine $D$ as follows. On input $n \in \mathbb{N}$, for each stage $s \in \mathbb{N}$, simulate $M_1(n)$ for $s$ steps and simulate $M_0(n)$ for $s$ steps, both from their initial configurations on input $n$. If the stage-$s$ simulation of $M_1(n)$ has halted, then output $1$ and halt. If the stage-$s$ simulation of $M_0(n)$ has halted, then output $0$ and halt. [guided] We now build a decider from two recognizers. The difficulty is that a recognizer may fail to halt on inputs outside its language, so we cannot run $M_1(n)$ to completion first and then run $M_0(n)$ afterward: if $n \notin A$, the first computation may run forever and we would never reach the recognizer for the complement. The remedy is dovetailing. Define a Turing machine $D$ with input set $\mathbb{N}$ and output set $\{0,1\}$. On input $n \in \mathbb{N}$, the machine $D$ performs stages indexed by $s \in \mathbb{N}$. At stage $s$, it simulates $M_1(n)$ for $s$ computation steps starting from the initial configuration of $M_1$ on input $n$, and it also simulates $M_0(n)$ for $s$ computation steps starting from the initial configuration of $M_0$ on input $n$. If the simulated run of $M_1(n)$ has halted by then, $D$ outputs $1$ and halts. If the simulated run of $M_0(n)$ has halted by then, $D$ outputs $0$ and halts. This procedure is computable because finite simulations of Turing machines are effective: for fixed $s$, the machine performs only finitely many transition steps of $M_1$ and $M_0$. It remains to prove that $D$ always halts and returns the correct value. Fix $n \in \mathbb{N}$. Since $A$ and $\mathbb{N} \setminus A$ form a partition of $\mathbb{N}$, exactly one of the two alternatives holds: \begin{align*} n \in A \qquad\text{or}\qquad n \in \mathbb{N} \setminus A. \end{align*} If $n \in A$, then $M_1(n)$ halts because $M_1$ recognizes $A$, while $M_0(n)$ does not halt because $n \notin \mathbb{N} \setminus A$. Let $t \in \mathbb{N}$ be the number of steps after which $M_1(n)$ halts. At every stage $s \geq t$, the stage-$s$ simulation detects that halt, so $D(n)$ outputs $1$ and halts. This output equals $\mathbb{1}_A(n)$. If $n \in \mathbb{N} \setminus A$, then $M_0(n)$ halts because $M_0$ recognizes $\mathbb{N} \setminus A$, while $M_1(n)$ does not halt because $n \notin A$. Let $t \in \mathbb{N}$ be the number of steps after which $M_0(n)$ halts. At every stage $s \geq t$, the stage-$s$ simulation detects that halt, so $D(n)$ outputs $0$ and halts. This output again equals $\mathbb{1}_A(n)$. Thus $D$ halts on every input $n \in \mathbb{N}$ and computes the characteristic function $\mathbb{1}_A: \mathbb{N} \to \{0,1\}$. [/guided] Fix $n \in \mathbb{N}$. Since $A$ and $\mathbb{N} \setminus A$ are complementary subsets of $\mathbb{N}$, exactly one of $n \in A$ and $n \in \mathbb{N} \setminus A$ holds. If $n \in A$, then $M_1(n)$ halts; if it halts after $t$ steps, the simulation at every stage $s \geq t$ detects this and $D(n)$ outputs $1$. If $n \in \mathbb{N} \setminus A$, then $M_0(n)$ halts; if it halts after $t$ steps, the simulation at every stage $s \geq t$ detects this and $D(n)$ outputs $0$. Therefore $D$ halts on every input and computes $\mathbb{1}_A$. [/step] [step:Conclude the equivalence] The first step shows that computability of $A$ implies computable enumerability of both $A$ and $\mathbb{N} \setminus A$. The second step shows that computable enumerability of both $A$ and $\mathbb{N} \setminus A$ gives a total computable characteristic function $\mathbb{1}_A: \mathbb{N} \to \{0,1\}$. Hence $A$ is computable if and only if both $A$ and $\mathbb{N} \setminus A$ are computably enumerable. [/step]