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.

Title	primitive recursive function
Canonical name	PrimitiveRecursiveFunction
Date of creation	2013-03-22 12:33:19
Last modified on	2013-03-22 12:33:19
Owner	CWoo (3771)
Last modified by	CWoo (3771)
Numerical id	19
Author	CWoo (3771)
Entry type	Definition
Classification	msc 03D20
Synonym	primitive recursive
Related topic	RecursiveFunction
Defines	primitive recursive set
Defines	primitive recursive predicate
Defines	partial primitive recursive function