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 $\boldsymbol{x}\in\mathbb{N}^{m}$ and $y\in\mathbb{N}$:

 $f_{s}(\boldsymbol{x},y):=\sum_{i=0}^{y}f(\boldsymbol{x},i)$
 $f_{p}(\boldsymbol{x},y):=\prod_{i=0}^{y}f(\boldsymbol{x},i)$

These are easily seen to be primitive recursive, because they are defined by primitive recursion. For example,

 $f_{s}(\boldsymbol{x},0)=f(\boldsymbol{x},0),\quad\mbox{and}\quad f_{s}(% \boldsymbol{x},n+1)=g(\boldsymbol{x},n,f_{s}(\boldsymbol{x},n)),$

where $g(\boldsymbol{x},n,y)=\operatorname{add}(f(\boldsymbol{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}(\boldsymbol{x},y):=\{z\in\mathbb{N}\mid z\leq y\mbox{ and }f(\boldsymbol% {x},z)=0\}.$

Define

 $f_{bmin}(\boldsymbol{x},y):=\left\{\begin{array}[]{ll}\min A_{f}(\boldsymbol{x% },y)&\textrm{if }A_{f}(\boldsymbol{x},y)\neq\varnothing,\\ s(y)&\textrm{otherwise.}\end{array}\right.$

$f_{bmin}$ is called the function obtained from $f$ by bounded minimization, and is usually denoted

 $\mu z\leq y(f(\boldsymbol{x},z)=0).$
Proposition 1.

If $f:\mathbb{N}^{m+1}\to\mathbb{N}$ is primitive recursive, so is $f_{bmin}$.

Proof.

Define $g:=\operatorname{sgn}\circ f$. Then

 $g(\boldsymbol{x},y):=\left\{\begin{array}[]{ll}0&\textrm{if }f(\boldsymbol{x},% y)=0,\\ 1&\textrm{otherwise.}\end{array}\right.$

As $f$ is primitive recursive, so is $g$, since the sign function $\operatorname{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}(\boldsymbol{x},y)=1$, then $g_{p}(\boldsymbol{x},z)=1$ for all $z,

• if $g_{p}(\boldsymbol{x},y)=0$, then $g_{p}(\boldsymbol{x},z)=0$ for all $z\geq y$.

Finally, the function $(g_{p})_{s}$ obtained from $g_{p}$ by bounded sum has the property that, when applied to $(\boldsymbol{x},y)$, counts the number of $z\leq y$ such that $g_{p}(\boldsymbol{x},z)=1$. Based on the property of $g_{p}$, this count is then exactly the least $z\leq y$ such that $g_{p}(\boldsymbol{x},z)=1$. This means that $(g_{p})_{s}=f_{bmin}$ for all $(\boldsymbol{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.

 Title bounded minimization Canonical name BoundedMinimization Date of creation 2013-03-22 19:05:18 Last modified on 2013-03-22 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