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. 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. 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 number-theoretic 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.

Corollary 1.

If $f$ is defined by course-of-values recursion via an elementary recursive function $h$, and $f$ is bounded from above by an elementary recursive function $k$, then $f$ is elementary recursive.

Title bounded recursion BoundedRecursion 2013-03-22 19:07:01 2013-03-22 19:07:01 CWoo (3771) CWoo (3771) 5 CWoo (3771) Definition msc 03D20 bounded primitive recursion ElementaryRecursiveFunction