bounded minimization
One useful way of generating more primitive recursive functions^{} from existing ones is through what is known as bounded summation and bounded product. Given a primitive recursive function $f:{\mathbb{N}}^{m+1}\to \mathbb{N}$, define two functions ${f}_{s},{f}_{p}:{\mathbb{N}}^{m+1}\to \mathbb{N}$ as follows: for $\bm{x}\in {\mathbb{N}}^{m}$ and $y\in \mathbb{N}$:
$${f}_{s}(\bm{x},y):=\sum _{i=0}^{y}f(\bm{x},i)$$ 
$${f}_{p}(\bm{x},y):=\prod _{i=0}^{y}f(\bm{x},i)$$ 
These are easily seen to be primitive recursive, because they are defined by primitive recursion. For example,
$${f}_{s}(\bm{x},0)=f(\bm{x},0),\text{and}\mathit{\hspace{1em}}{f}_{s}(\bm{x},n+1)=g(\bm{x},n,{f}_{s}(\bm{x},n)),$$ 
where $g(\bm{x},n,y)=\mathrm{add}(f(\bm{x},n),y)$, which is primitive recursive by functional^{} composition^{}.
Definition. We call ${f}_{s}$ and ${f}_{p}$ functions obtained from $f$ by bounded sum and bounded product respectively.
Using bounded summation and bounded product, another useful class of primitive recursive functions can be generated:
Definition. Let $f:{\mathbb{N}}^{m+1}\to \mathbb{N}$ be a function. For each $y\in \mathbb{N}$, set
$${A}_{f}(\bm{x},y):=\{z\in \mathbb{N}\mid z\le y\text{and}f(\bm{x},z)=0\}.$$ 
Define
$${f}_{bmin}(\bm{x},y):=\{\begin{array}{cc}\mathrm{min}{A}_{f}(\bm{x},y)\hfill & \text{if}{A}_{f}(\bm{x},y)\ne \mathrm{\varnothing},\hfill \\ s(y)\hfill & \text{otherwise.}\hfill \end{array}$$ 
${f}_{bmin}$ is called the function obtained from $f$ by bounded minimization, and is usually denoted
$$\mu z\le y(f(\bm{x},z)=0).$$ 
Proposition 1.
If $f\mathrm{:}{\mathrm{N}}^{m\mathrm{+}\mathrm{1}}\mathrm{\to}\mathrm{N}$ is primitive recursive, so is ${f}_{b\mathit{}m\mathit{}i\mathit{}n}$.
Proof.
Define $g:=\mathrm{sgn}\circ f$. Then
$$g(\bm{x},y):=\{\begin{array}{cc}0\hfill & \text{if}f(\bm{x},y)=0,\hfill \\ 1\hfill & \text{otherwise.}\hfill \end{array}$$ 
As $f$ is primitive recursive, so is $g$, since the sign function $\mathrm{sgn}$ is primitive recursive (see this entry (http://planetmath.org/ExamplesOfPrimitiveRecursiveFunctions)).
Next, the function ${g}_{p}$ obtained from $g$ by bounded product has the following properties:

•
if ${g}_{p}(\bm{x},y)=1$, then ${g}_{p}(\bm{x},z)=1$ for all $$,

•
if ${g}_{p}(\bm{x},y)=0$, then ${g}_{p}(\bm{x},z)=0$ for all $z\ge y$.
Finally, the function ${({g}_{p})}_{s}$ obtained from ${g}_{p}$ by bounded sum has the property that, when applied to $(\bm{x},y)$, counts the number of $z\le y$ such that ${g}_{p}(\bm{x},z)=1$. Based on the property of ${g}_{p}$, this count is then exactly the least $z\le y$ such that ${g}_{p}(\bm{x},z)=1$. This means that ${({g}_{p})}_{s}={f}_{bmin}$ for all $(\bm{x},y)\in {\mathbb{N}}^{m+1}$. Since ${g}_{p}$ is primitive recursive, so is ${({g}_{p})}_{s}$, or that ${f}_{bmin}$ is primitive recursive. ∎
In fact, if $f$ is a (total) recursive function, so is ${f}_{bmin}$, because all of the derived functions in the proof above preserve primitive recursiveness as well as totalness.
Remarks.

•
In the definition of bounded minimization, if we take the $y$ out, then we arrive at the notion of unbounded minimization, or just minimization. The proposition^{} above shows that the set $\mathcal{P}\mathcal{R}$ of primitive recursive functions is closed under bounded minimization. However, $\mathcal{P}\mathcal{R}$ is not closed under minimization. The closure of $\mathcal{P}\mathcal{R}$ under minimization is the set $\mathcal{R}$ of recursive functions (total or not).

•
It is not hard to show that $\mathcal{E}\mathcal{R}$, the set of all elementary recursive functions, is closed under bounded minimization.
Title  bounded minimization 
Canonical name  BoundedMinimization 
Date of creation  20130322 19:05:18 
Last modified on  20130322 19:05:18 
Owner  CWoo (3771) 
Last modified by  CWoo (3771) 
Numerical id  11 
Author  CWoo (3771) 
Entry type  Definition 
Classification  msc 03D20 
Synonym  bounded sum 
Related topic  UnboundedMinimization 
Related topic  RecursiveFunction 
Related topic  BoundedMaximization 
Defines  bounded summation 
Defines  bounded product 