[proofplan] We prove the equivalence by converting between three kinds of semidecision data. An enumerator gives a recognizer by dovetailing all computations until the target value appears. A domain recognizer gives an enumerator by dovetailing all inputs and printing the inputs whose computations halt. Finally, a halting computation can be encoded by a computable bounded-stage relation, and any computable existential relation gives a recognizer by searching for a witness. [/proofplan] [step:Turn an enumeration into a partial computable recognizer for membership] Assume $A$ is computably enumerable. Let $\varphi: \mathbb{N} \rightharpoonup \mathbb{N}$ be a partial computable function with $A = \operatorname{range}(\varphi)$. Define a partial function \begin{align*} \psi: \mathbb{N} \rightharpoonup \mathbb{N} \end{align*} by the following algorithm on input $n \in \mathbb{N}$. At stage $s \in \mathbb{N}$, simulate the first $s$ computation steps of $\varphi(k)$ for each $k \leq s$. If, for some $k \leq s$, that simulation has halted with output $n$, halt and output $1$. If no such $k$ is found, continue to stage $s+1$. This algorithm is effective because each stage performs only finitely many finite simulations. Hence $\psi$ is partial computable. If $n \in A$, then $n \in \operatorname{range}(\varphi)$, so there exists $k \in \mathbb{N}$ such that $\varphi(k)\downarrow = n$. Let $t \in \mathbb{N}$ be the number of computation steps after which $\varphi(k)$ halts with output $n$. At every stage $s \geq \max\{k,t\}$, the dovetailing simulation includes the input $k$ for at least $t$ steps, so the algorithm defining $\psi(n)$ halts. Therefore $n \in \operatorname{dom}(\psi)$. Conversely, if $n \in \operatorname{dom}(\psi)$, then the algorithm halted at some finite stage $s$. By the halting condition, there exists $k \leq s$ such that the simulated computation of $\varphi(k)$ halted with output $n$. Hence $\varphi(k)\downarrow = n$, so $n \in \operatorname{range}(\varphi) = A$. Thus $A = \operatorname{dom}(\psi)$. [/step] [step:Turn a partial computable domain into a computably enumerable range] Assume there exists a partial computable function $\psi: \mathbb{N} \rightharpoonup \mathbb{N}$ such that $A = \operatorname{dom}(\psi)$. Define a partial computable function \begin{align*} \varphi: \mathbb{N} \rightharpoonup \mathbb{N} \end{align*} as follows. Interpret an input $j \in \mathbb{N}$ as coding a pair $(n,s) \in \mathbb{N} \times \mathbb{N}$ under a fixed computable pairing function. On input $j$, decode $j$ as $(n,s)$, simulate $\psi(n)$ for exactly $s$ computation steps, and output $n$ if that simulation halts within those $s$ steps. If the simulation has not halted within $s$ steps, diverge. Because decoding $j$ and simulating $\psi(n)$ for a bounded number of steps are effective operations, $\varphi$ is partial computable. If $m \in \operatorname{range}(\varphi)$, then for some coded pair $(n,s)$ the computation $\varphi(j)$ halts with output $m$. By construction this output is $n$, so $m=n$, and the computation $\psi(n)$ halts within $s$ steps. Hence $m=n \in \operatorname{dom}(\psi)=A$. If $m \in A$, then $m \in \operatorname{dom}(\psi)$, so $\psi(m)$ halts after some number $t \in \mathbb{N}$ of computation steps. Let $j \in \mathbb{N}$ be the code of the pair $(m,t)$. On input $j$, the function $\varphi$ simulates $\psi(m)$ for $t$ steps and therefore halts with output $m$. Hence $m \in \operatorname{range}(\varphi)$. Therefore $A = \operatorname{range}(\varphi)$, so $A$ is computably enumerable. [guided] The goal is to convert a recognizer for membership in $A$ into an enumerator whose outputs are exactly the elements of $A$. The recognizer is the partial computable function $\psi$: it halts exactly on the elements of $A$, but it may never halt outside $A$. Since we cannot simply run $\psi(1),\psi(2),\dots$ one after another, we use bounded simulations. Fix a computable pairing function that codes each pair $(n,s) \in \mathbb{N} \times \mathbb{N}$ by a single natural number $j \in \mathbb{N}$, and whose decoding functions are computable. Define \begin{align*} \varphi: \mathbb{N} \rightharpoonup \mathbb{N} \end{align*} as follows. Given $j \in \mathbb{N}$, decode it as $(n,s)$. Simulate the computation $\psi(n)$ for exactly $s$ steps. If that bounded simulation halts, output $n$. If it does not halt within those $s$ steps, let the computation of $\varphi(j)$ diverge. This is a partial computable function because every operation before the possible divergence is effective: decoding $j$ is computable, and a simulation for exactly $s$ steps is a finite mechanical procedure. We now check that the range is exactly $A$. First suppose $m \in \operatorname{range}(\varphi)$. Then there exists an input $j \in \mathbb{N}$ such that $\varphi(j)\downarrow = m$. Decode $j$ as $(n,s)$. The only way $\varphi(j)$ can halt is that the bounded simulation of $\psi(n)$ halts within $s$ steps, and in that case the output is exactly $n$. Therefore $m=n$, and $\psi(m)=\psi(n)$ halts. Since $A=\operatorname{dom}(\psi)$, this gives $m \in A$. Conversely suppose $m \in A$. Since $A=\operatorname{dom}(\psi)$, the computation $\psi(m)$ halts. Let $t \in \mathbb{N}$ be a number of computation steps sufficient for this halting computation. Let $j$ be the code of the pair $(m,t)$. On input $j$, the machine for $\varphi$ decodes $(m,t)$, simulates $\psi(m)$ for $t$ steps, sees the halt, and outputs $m$. Hence $m \in \operatorname{range}(\varphi)$. Thus every output of $\varphi$ lies in $A$, and every element of $A$ is eventually output by $\varphi$. Therefore $A=\operatorname{range}(\varphi)$, so $A$ is computably enumerable. [/guided] [/step] [step:Encode a partial computable domain by a computable existential relation] Assume there exists a partial computable function $\psi: \mathbb{N} \rightharpoonup \mathbb{N}$ with $A = \operatorname{dom}(\psi)$. Define a relation $R \subseteq \mathbb{N} \times \mathbb{N}$ by \begin{align*} R(n,s) \iff \text{the computation } \psi(n) \text{ halts within } s \text{ steps}. \end{align*} For fixed $n,s \in \mathbb{N}$, this condition is decidable by simulating $\psi(n)$ for exactly $s$ steps. Hence $R$ is computable. For every $n \in \mathbb{N}$, if $n \in A$, then $\psi(n)$ halts, so there exists $s \in \mathbb{N}$ such that $\psi(n)$ halts within $s$ steps, and therefore $R(n,s)$. Conversely, if $\exists s \in \mathbb{N}\ R(n,s)$, then $\psi(n)$ halts within $s$ steps, so $n \in \operatorname{dom}(\psi)=A$. Thus \begin{align*} n \in A \iff \exists s \in \mathbb{N}\ R(n,s). \end{align*} [/step] [step:Search a computable existential relation to obtain a partial computable domain] Assume there exists a computable relation $R \subseteq \mathbb{N} \times \mathbb{N}$ such that, for every $n \in \mathbb{N}$, \begin{align*} n \in A \iff \exists s \in \mathbb{N}\ R(n,s). \end{align*} Define a partial function \begin{align*} \psi: \mathbb{N} \rightharpoonup \mathbb{N} \end{align*} by the following algorithm on input $n \in \mathbb{N}$. Search through all possible witnesses $s \in \mathbb{N}$ in the fixed effective order $0,1,2,\dots$ when $0 \in \mathbb{N}$, and otherwise in the order $1,2,3,\dots$. For each $s$, decide whether $R(n,s)$ holds. If $R(n,s)$ holds for some $s$, halt and output $1$; otherwise continue. Since $R$ is computable, each individual test $R(n,s)$ is decidable, so this search procedure defines a partial computable function. If $n \in A$, then by hypothesis there exists $s \in \mathbb{N}$ such that $R(n,s)$ holds. The search eventually reaches that $s$ and halts, so $n \in \operatorname{dom}(\psi)$. If $n \in \operatorname{dom}(\psi)$, then the algorithm halted after finding some $s \in \mathbb{N}$ with $R(n,s)$, so by the defining equivalence for $R$, we have $n \in A$. Hence $A = \operatorname{dom}(\psi)$. [/step] [step:Combine the implications] The first step proves that condition 1 implies condition 2. The second step proves that condition 2 implies condition 1. The third step proves that condition 2 implies condition 3. The fourth step proves that condition 3 implies condition 2. Therefore conditions 1, 2, and 3 are equivalent. [/step]