3

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?

Evinda
  • 1,460

2 Answers2

2

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}$.

Maanroof
  • 524
  • 2
  • 12
  • Pedantic point: such an $m$ might not exist. The problem statement isn't sufficiently careful. The domain of a partial recursive is recursively enumerable, and such sets are either the range of a total recursive function, or they are empty. The latter can't be ruled out a-priori. But, still, +1. – John Coleman Aug 27 '16 at 16:06
  • Could you explain to me further the definition of $f(n)$ ? How do we show like that , that the domain of any partially defined recursive function is equal to the range of some ( totally defined ) recursive function? I haven't really understood it... – Evinda Aug 27 '16 at 19:56
  • The idea is that, assuming your partial recursive function $\varphi_e$ is not empty, we pick some element $m$ in its domain. Then we use an effective enumeration of all partial computable functions and an effective bijection between $\mathbb{N}$ and finite sequences in $\mathbb{N}$ to construct the desired total function $f$. We know for a given $k$, if $\varphi_e(k)$ converges, then it does so in a finite number of steps, say $s$, hence for $n$ such that $((n)_0,(n)_1) = (k,s)$ it holds $f(n) = k$. The converse should be doable now, I hope. – Maanroof Aug 27 '16 at 20:06
0

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.

Dino Rossegger
  • 220