You are here
Homebounded recursion
Primary tabs
bounded recursion
In this entry, the following notations are used:
$\mathcal{F}=\bigcup\{F_{k}\mid k\in\mathbb{N}\}$, where for each $k\in\mathbb{N}$, and $F_{k}=\{f\mid f\colon\mathbb{N}^{{k}}\to\mathbb{N}\}$.
Definition. A function $f\in F_{{m+1}}$ is said to be defined by bounded recursion via functions $g\in F_{m}$, $h\in F_{{m+2}}$, and $k\in F_{{m+1}}$ if, for any $\boldsymbol{x}\in\mathbb{N}^{m}$ and $y\in\mathbb{N}$,
1. $f$ is defined by primitive recursion via $g$ and $h$:

$f(\boldsymbol{x},0)=g(\boldsymbol{x})$,

$f(\boldsymbol{x},y+1)=h(\boldsymbol{x},y,f(\boldsymbol{x},y))$;

2. $f$ is bounded from above by $k$:

$f(\boldsymbol{x},y)\leq k(\boldsymbol{x},y)$.

Clearly, a function that is defined by bounded recursion is defined by primitive recursion. Conversely, a function is defined by primitive recursion, it is also defined by bounded recursion, since it is bounded by itself. However, the two concepts are not exactly the same. To make this precise, we first define what it means for a set of numbertheoretic functions be closed under bounded recursion:
Definition. A set $\mathcal{B}\subseteq\mathcal{F}$ is said to be closed under bounded recursion if, for any $f$ defined by bounded recursion via $g,h,k\in\mathcal{B}$, then $f\in\mathcal{B}$.
It is clear that $\mathcal{F}$ is closed under both primitive recursion and bounded recursion, and so are $\mathcal{PR}$, the set of all primitive recursive functions, as well as $\mathcal{R}\cap\mathcal{F}$, the set of all total recursive functions. However,
Proposition 1.
The set $\mathcal{ER}$ of all elementary recursive functions is closed under bounded recursion, but not primitive recursion.
Since the exponential function, the $i$th prime function, and the function $(x)_{y}$ (the exponent of $y$ in $x$) are elementary recursive, we have the following corollary:
Corollary 1.
If $f$ is defined by courseofvalues recursion via an elementary recursive function $h$, and $f$ is bounded from above by an elementary recursive function $k$, then $f$ is elementary recursive.
Mathematics Subject Classification
03D20 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
 Corrections