It is customary to define the class of [partial recursive functions](https://en.wikipedia.org/wiki/Mu-recursive_function) by taking the set of [primitive recursive functions](https://en.wikipedia.org/wiki/Primitive_recursive) $PR$ and taking closure over unbound search operation.


Do we need the "whole" set of primitive recursive functions as a base to reach the class of partial recursive functions with the closure? It seems reasonable to assume that unbound search could be used in the place of primitive recursion to reach the class $PR$ from a smaller base class.


For example Grzegorczyk proves that



> 
> 
> > 
> > Every computable function can be presented in the form $f(u)=A(ix[B(u,x)=0])$, where
> > $A$ and $B$ are functions of the class $\mathcal{E}\_0$.
> > 
> > 
> > 
> 
> 
> 


Here $ix[B(u,x)=0]$ is the unique $x$ such that $B(u,x)=0$ and $\mathcal{E}\_0$ is the lowest set in [Grzegorczyk-hierarchy](https://en.wikipedia.org/wiki/Grzegorczyk_hierarchy). I don't, however, see how to change the "unique $x$ such.." to "smallest $x$ such..".



Smallest base to reach partial recursive functions as a closure of unbound search
$\def\dotm{\mathbin{\scriptstyle\dot{\smash{\textstyle-}}}}$It follows from the MRDP theorem that every partial recursive function $f(\vec x)$ can be written as
$$f(\vec x)\simeq l\bigl(\mu z\,[p(\vec x,l(z),l(r(z)),\dots,l(r^{k-1}(z)),r^k(z))=0]\bigr),$$
where $p(\vec x,y\_0,\dots,y\_k)$ is a polynomial with integer coefficients, and $l(z)$ and $r(z)$ are the left and right inverse of a pairing function. If we take the Cantor pairing function
$$[x,y]=\frac{(x+y)(x+y+1)}2+x,$$ we can express $l(z)=z-[0,g(z)]$, $r(z)=g(z)-l(z)$, where $g(z)=\mu u\,[2z\dotm(u+1)(u+2)=0]$. Thus, partial recursive functions are the closure of projections, successor, multiplication, and limited subtraction under minimization and composition. (Note that $x+y=S(x)S(y)\dotm ((S(x)S(y)\dotm x)\dotm y)$.)


