I am trying to prove that a certain function is partial recursive. Suppose we have fixed primitive recursive $g:\mathbb{N} \rightarrow \mathbb{N}$ and for each $d$ let $f_d:\mathbb{N}\rightarrow \mathbb{N}$ be primitive recursive. Let $f:\mathbb{N} \rightarrow \mathbb{N}$ so that for any $d$ we have $f(x)=f_d(x)$ if $g(x)=d$. I want to prove that this function is partial recursive. I think this should follow from the fact that $f(x)=\mu y (g(x)=d \land f_d(x)=y)$ where $\mu$ is the unbounded search, and the fact that $g$ and $f_d$ are primitive recursive. Am I missing something here?
5
- 1$\begingroup$ If your functions $(f_d)_{d\in\omega}$ are uniformly primitive recursive, then yes, f is primitive recursive. For example, let $F(d,x)$ be primitive recursive with $F(d,x)=f_d(x)$, then $f(x)=F(g(x),x)$. Also, the class of primitive recursive functions is not, in general, closed under the $\mu$-operator. $\endgroup$Alvaro Pintado– Alvaro Pintado2025-09-14 21:58:11 +00:00Commented Sep 14 at 21:58
- 3$\begingroup$ Your definition of $f$ only works for one value of $d.$ In general this is false unless you have some notion of computability in the variable $d,$ e.g. if $f_d(x)= h(d,x)$ for some computable function $h$. (Otherwise, e.g. if you take $h(x)$ to be any non-computable function, then let $g(x)=x$ and $f_d(x)=h(d)$, then $f_d$ is constant, so p.r, and $g(x)$ is p.r., but $f(x) = h(x)$.) $\endgroup$spaceisdarkgreen– spaceisdarkgreen2025-09-14 21:58:35 +00:00Commented Sep 14 at 21:58
- $\begingroup$ @AlvaroPintado I only want f to be partial recursive which is a class of functions closed under the $\mu$-operation. No? $\endgroup$medvjed– medvjed2025-09-14 22:21:22 +00:00Commented Sep 14 at 22:21
- 3$\begingroup$ As others have pointed out, there is a uniformity problem: the natural thing you would do to compute $f(x)$ is: first compute $g(x)$, obtain $d$, then compute $f_d(x)$. In particular, you are trying to compute the map $(x,d) \mapsto f_d(x)$. However you only assumed that $f_d$ is computable, not that the functions $\{f_d\}_d$ are uniformly computable. In other words, each $f_d$ has its algorithm, but nobody says that there is a single algorithm that, given $d$, simulates $f_d$. The uniformity is very much needed, otherwise the claim is false. $\endgroup$Manlio– Manlio2025-09-15 14:46:01 +00:00Commented Sep 15 at 14:46
- $\begingroup$ @medvjed Yes, sorry, I misread "partial recursive" as "primitive recursive". $\endgroup$Alvaro Pintado– Alvaro Pintado2025-09-15 18:50:18 +00:00Commented Sep 15 at 18:50
Add a comment |
1 Answer
$\begingroup$ $\endgroup$
First off, I'll read every instance of "partial recursive" to mean "primitive recursive", since there is nothing in this description that could possibly introduce undefined values (like unbounded loops would). And anyway the real difficulty does not lie in this distinction.
But the answer clearly has to be "no", this is not a valid way to build a recursive function, primitive or otherwise. And rightly so, because the whole purpose of talking about recursive functions is to fix a class of functions that, despite the fact the they potentially compute infinitely many values, are given by a finite specification. If you were allowed to use infinite specifications, then every function $\Bbb{N}\to\Bbb{N}$ could be defined, by simply tabulating all its values. Your description requires an infinite amount of data to specify all of the functions $f_d$, so you should immediately suspect this can be used to define an arbitrary function. Indeed, if for simplicity one takes $g$ to be the identity function, then each function $f_d$ serves only to provide a single value $f_d(d)$, and the fact that $f_d$ is required to be primitive recursive does not give you anything useful. Indeed you might as well suppose that each $f_d$ is a constant function (which is certainly primitive recursive), and that still leaves the possibility to specify each of the infinitely many values $f_d(d)$ separately, as $d$ varies over $\Bbb N$, and this accommodates an arbitrary function for $f$.
The uniformity requirement mentioned in the comments that would fix this serves precisely to force all $f_d$ to be defined at once by a single, finite, description.
