## You are here

Homeprimitive recursive function

## Primary tabs

# 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.
- 2.
(successor function) $s\in\mathcal{PR}\cap F_{1}$, given by $s(n):=n+1$;

- 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.
$\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.
$\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.

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] 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] 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] 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.

## Mathematics Subject Classification

03D20*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections

## Attached Articles

examples of primitive recursive functions by CWoo

bounded minimization by CWoo

importance of primitive recursion by CWoo

examples of primitive recursive predicates by CWoo

course-of-values recursion by CWoo

mutual recursion by CWoo

primitive recursive functions without primitive recursion by CWoo

definition by cases by CWoo