# primitive recursive function

To define what a primitive recursive function is, the following notations are used:

$\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 primitive recursive functions is the smallest subset $\mathcal{PR}$ of $\mathcal{F}$ where:

1. 1.

(zero function) $z\in\mathcal{PR}\cap F_{1}$, given by $z(n):=0$;

2. 2.

(successor function) $s\in\mathcal{PR}\cap F_{1}$, given by $s(n):=n+1$;

3. 3.

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

4. 4.

$\mathcal{PR}$ is closed under composition: If $\{g_{1},\ldots,g_{m}\}\subseteq\mathcal{PR}\cap F_{k}$ and $h\in\mathcal{PR}\cap F_{m}$, then $f\in\mathcal{PR}\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}));$
5. 5.

$\mathcal{PR}$ is closed under primitive recursion: If $g\in\mathcal{PR}\cap F_{k}$ and $h\in\mathcal{PR}\cap F_{k+2}$, then $f\in\mathcal{PR}\cap F_{k+1}$, where

 $\displaystyle f(n_{1},\ldots,n_{k},0)$ $\displaystyle=$ $\displaystyle g(n_{1},\ldots,n_{k})$ $\displaystyle f(n_{1},\ldots,n_{k},s(n))$ $\displaystyle=$ $\displaystyle h(n_{1},\ldots,n_{k},n,f(n_{1},\ldots,n_{k},n)).$

Many of the arithmetic functions that we encounter in basic math are primitive recursive, including addition, multiplication, and exponentiation. More examples can be found in this entry (http://planetmath.org/ExamplesOfPrimitiveRecursiveFunctions).

Primitive recursive functions are computable by Turing machines. In fact, it can be shown that $\mathcal{PR}$ is precisely the set of functions computable by programs using FOR NEXT loops. However, not all Turing-computable functions are primitive recursive: the Ackermann function is one such example.

Since $\mathcal{F}$ is countable, so is $\mathcal{PR}$. Moreover, $\mathcal{PR}$ is recursively enumerable (can be listed by a Turing machine).

Remarks.

1. [1]

Every primitive recursive function is total, since it is built from $z$, $s$, and $p^{k}_{m}$, each of which is total, and that functional composition, and primitive recursion preserve totalness. By including $\varnothing$ in $\mathcal{PR}$ above, and close it by functional composition and primitive recursion, one gets the set of partial primitive recursive functions.

2. [2]

Primitive recursiveness can be defined on subsets of $\mathbb{N}^{k}$: a subset $S\subseteq\mathbb{N}^{k}$ is primitive recursive if its characteristic function $\varphi_{S}$, which is defined as

 $\varphi_{S}(x):=\left\{\begin{array}[]{ll}1&\textrm{if }x\in S,\\ 0&\textrm{otherwise.}\end{array}\right.$

is primitive recursive.

3. [3]

Likewise, primitive recursiveness can be defined for predicates over tuples of natural numbers. A predicate $\Phi(\boldsymbol{x})$, where $\boldsymbol{x}\in\mathbb{N}^{k}$, is said to be primitive recursive if the set $S(\Phi):=\{\boldsymbol{x}\mid\Phi(\boldsymbol{x})\}$ is primitive recursive.

Title primitive recursive function PrimitiveRecursiveFunction 2013-03-22 12:33:19 2013-03-22 12:33:19 CWoo (3771) CWoo (3771) 19 CWoo (3771) Definition msc 03D20 primitive recursive RecursiveFunction primitive recursive set primitive recursive predicate partial primitive recursive function