primitive recursive function

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

$ℱ=\bigcup \{F_k\mid k\in \mathbb{N}\}$, where for each $k\in \mathbb{N}\text{, }{F}_k=\{f\mid f:{\mathbb{N}}^k\to \mathbb{N}\}$.

Definition. The set of primitive recursive functions is the smallest subset $𝒫ℛ$ of $ℱ$ where:

1. (zero function) $z\in 𝒫ℛ\cap F_1$, given by $z(n):=0$;

2. (successor function) $s\in 𝒫ℛ\cap F_1$, given by $s(n):=n+1$;

3. (projection functions) $p_m^k\in 𝒫ℛ\cap F_k$, where $m\le k$, given by $p_m^k(n_1,\mathrm{\dots },n_k):=n_m$;

4. $𝒫ℛ$ is closed under composition: If $\{g_1,\mathrm{\dots },g_m\}\subseteq 𝒫ℛ\cap F_k$ and $h\in 𝒫ℛ\cap F_m$, then $f\in 𝒫ℛ\cap F_k$, where

   $$f(n_1,\mathrm{\dots },n_k)=h(g_1(n_1,\mathrm{\dots },n_k),\mathrm{\dots },g_m(n_1,\mathrm{\dots },n_k));$$

5. $𝒫ℛ$ is closed under primitive recursion: If $g\in 𝒫ℛ\cap F_k$ and $h\in 𝒫ℛ\cap F_{k+2}$, then $f\in 𝒫ℛ\cap F_{k+1}$, where

   $f(n_1,\mathrm{\dots },n_k,0)$$=$$g(n_1,\mathrm{\dots },n_k)$

   $f(n_1,\mathrm{\dots },n_k,s(n))$$=$$h(n_1,\mathrm{\dots },n_k,n,f(n_1,\mathrm{\dots },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 $𝒫ℛ$ 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 $ℱ$ is countable, so is $𝒫ℛ$. Moreover, $𝒫ℛ$ is recursively enumerable (can be listed by a Turing machine).

Remarks.

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

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 ${\phi }_S$, which is defined as

   is primitive recursive.

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