Recursive functions

Question

I want to show that the domain of any partially defined recursive function is equal to the range of some ( totally defined ) recursive function.

I haven't understood which is the difference between a partially defined recursive function and a totally defined recursive function? Could you explain it to me?

Answer 1

The difference is that a partial recursive function is partially defined. So it is an algorithm $\mathbb{N} \to \mathbb{N}$ for which there might by values $n\in \mathbb{N}$ that don't yield an answer, i.e. on which your algorithm is not defined.

For your question, write $\varphi_{e,s}$ for the $e$-th partial computable function, computed in $s$ steps. Then for a given $e$, consider \begin{align*} f(n) = \begin{cases} (n)_0; & \text{if } \varphi_{e,(n)_1}( (n)_0 ) \downarrow\\ m; &\text{else} \end{cases} \end{align*} for some fixed $m$ in the domain of $\varphi_e$. Here, $(n)_i$ is the $i$-th component of $n$ considered as finite sequence, for some recursive bijection between $\mathbb{N}$ and the set of finite sequences in $\mathbb{N}$.

Answer 2

Assume $f$ is partially recursive, say $f$ is $\varphi_e$ in an enumeration of the partial recursive functions. Then there exists a recursive enumeration of its domain, i.e., a set
$W_e$ such that $$x \in W_e \Leftrightarrow \varphi_e(x)\downarrow$$

There are two possibilities how $W_e$ looks like.

Case 1: $W_e \neq \emptyset$. Since $W_e$ is recursively enumerable, let $W_{e,s}$ be the set $W_e$ at stage $s$ of its enumeration. $W_{e,s}$ is recursive (check it). Then let $m$ be the first element enumerated into $W_e$, i.e., $m$ is the element in the first $W_{e,s}$ for $s\rightarrow \infty$ such that $W_{e,s}\neq \emptyset$. Then the function

$$ f(s)=\left\{\begin{array}{ll} x & \text{ if } x\in W_{e,s}\setminus W_{e,s-1} \\ m & \text{otherwise}\end{array}\right. $$ is recursive and has range $W_e$ (check it).

Case 2: As was pointed out in the comments of another answer such $m$ must not exist, i.e. $W_e$ is empty. But then $W_e$ is a recursive set because its characteristic function is just the constant function.