elementary recursive function

$\mathcal{F}=\bigcup\{F_{k}\mid k\in\mathbb{N}\}$, where for each $k\in\mathbb{N}\text{, }F_{k}=\{f\mid f\colon\mathbb{N}^{k}\to\mathbb{N}\}$.

Definition. The set of elementary recursive functions, or elementary functions for short, is the smallest subset $\mathcal{ER}$ of $\mathcal{F}$ where:

1. 1.

(addition) $\operatorname{add}\in\mathcal{ER}\cap F_{2}$, given by $\operatorname{add}(m,n):=m+n$;

2. 2.

(multiplication) $\operatorname{mult}\in\mathcal{ER}\cap F_{2}$, given by $\operatorname{mult}(m,n):=mn$;

3. 3.

(difference  ) $\operatorname{diff}\in\mathcal{ER}\cap F_{2}$, given by $\operatorname{diff}(m,n):=|m-n|$;

4. 4.

(quotient) $\operatorname{quo}\in\mathcal{ER}\cap F_{2}$, given by $\operatorname{quo}(m,n):=[m/n]$, which is the largest non-negative integer $z$ such that $nz\leq m$ (by convention, $\operatorname{quo}(0,0):=1$);

5. 5.

(projection) $p^{k}_{m}\in\mathcal{ER}\cap F_{k}$, where $m\leq k$, given by $p^{k}_{m}(n_{1},\ldots,n_{k}):=n_{m}$;

6. 6.

$\mathcal{ER}$ is closed under composition: If $\{g_{1},\ldots,g_{m}\}\subseteq\mathcal{ER}\cap F_{k}$ and $h\in\mathcal{ER}\cap F_{m}$, then $f\in\mathcal{ER}\cap F_{k}$, where

 $f(n_{1},\ldots,n_{k})=h(g_{1}(n_{1},\ldots,n_{k}),\ldots,g_{m}(n_{1},\ldots,n_% {k}));$
7. 7.

$\mathcal{ER}$ is closed under bounded sum: if $f\in\mathcal{ER}\cap F_{k}$, then $f_{s}\in\mathcal{ER}\cap F_{k}$, where

 $f_{s}(\boldsymbol{x},y):=\sum_{i=0}^{y}f(\boldsymbol{x},i);$
8. 8.

$\mathcal{ER}$ is closed under bounded product: if $f\in\mathcal{ER}\cap F_{k}$, then $f_{p}\in\mathcal{ER}\cap F_{k}$, where

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

Examples.

Remarks

• Consider the set $\mathcal{PR}$ of primitive recursive functions. The functions in the first five groups above are all in $\mathcal{PR}$. In addition, $\mathcal{PR}$ is closed under the operations in 6, 7, and 8 above, we see that $\mathcal{ER}\subseteq\mathcal{PR}$, since $\mathcal{ER}$, as defined, is the smallest such set.

• Furthermore, $\mathcal{ER}\neq\mathcal{PR}$. For example, the super-exponential function, given by $f(x,0)=m$, and $f(x,n+1)=\exp(m,f(x,n))$, where $m>1$, can be shown to be non-elementary.

• In addition, it can be shown that $\mathcal{ER}$ is the set of primitive recursive functions that can be obtained from the zero function, the successor function, and the projection functions via composition, and no more than three applications of primitive recursion.

• By taking the closure of $\mathcal{ER}$ with respect to unbounded minimization, one obtains $\mathcal{R}$, the set of all recursive functions (partial or total). In fact, by replacing bounded sum and bounded product with unbounded minimization, and the difference function with restricted subtraction, one obtains $\mathcal{R}$.

Title elementary recursive function ElementaryRecursiveFunction 2013-03-22 19:06:48 2013-03-22 19:06:48 CWoo (3771) CWoo (3771) 9 CWoo (3771) Definition msc 03D20 elementary BoundedRecursion elementary recursive