In recursion theory, by definition, a computably enumerable set (c.e.) is the range of a total computable function. However, I came across a textbook which asks to show how a c.e. set can also be the range of a partial computable function.
For instance, given a partial computable function $\phi_e$, with Godel number $e$, we have:
$$
\text{domain}(\phi_{g(e)}) = \text{range}(\phi_e)
$$
where $g(e)$ is a total computable function (i.e. the total computable function in the s-m-n theorem, where given a partial function $\Psi(e,x)$, where $e$ is a Godel number and $x$ is an input, we can construct another partial function $\phi_{g(e)}(x)$ that holds $e$ fixed using a total computable function $g(e)$).
But how can I show that there exists a total computable function $g(e)$ such that $\text{domain}(\phi_{g(e)}) = \text{range}(\phi_e)$ for a partial computable function $\phi_e(x)$?
Best Answer
Fixed $e$, we can consider the partial computable function $\psi$ that, upon input $y$, searches for a $x$ s.t. $\phi_e(x)=y$ and outputs $1$ if there is one and never halts otherwise. Clearly $\mathrm{range}(\phi_e)=\mathrm{domain}(\psi)$. Since an index for $\psi$ is computable from $e$ it is enough to consider the map $g$ that maps $e$ to an index for the corresponding $\psi$.