examples of primitive recursive functions

Starting from the simplest primitive recursive functions, we can build more complicated primitive recursive functions by functional composition and primitive recursion. In this entry, we have listed some basic examples using functional composition alone. In this entry, we list more basic examples, allowing the use of primitive recursion:

1.

$\operatorname{add}(x,y)=x+y$ : $\operatorname{add}(x,0)=\operatorname{id}(x)$ , and $\operatorname{add}(x,n+1)=s(\operatorname{add}(x,n))$
2.

$\operatorname{mult}(x,y)=xy$ : $\operatorname{mult}(x,0)=z(x)$ , and $\operatorname{mult}(x,n+1)=\operatorname{add}(x,\operatorname{mult}(x,n))$ .
3.

$p_{2}(x)=x^{2}$ , which is just $\operatorname{mult}(x,x)$ ; more generally, $p_{m+1}(x)=\operatorname{mult}(x,p_{m}(x))$ , which is primitive recursive by induction on $m$
4.

$\exp_{m}(x)=m^{x}$ : $\exp_{m}(0)=s(0)$ , and $\exp_{m}(n+1)=\operatorname{mult}(\operatorname{const}_{m}(n),\exp_{m}(n))$
5.

$\exp(x,y)=x^{y}$ : $\exp(x,0)=\operatorname{const}_{1}(x)$ , and $\exp(x,n+1)=\operatorname{mult}(x,\exp(x,n))$
6.

$\operatorname{fact}(x)=x!$ : $\operatorname{fact}(0)=s(0)$ , and $\operatorname{fact}(n+1)=\operatorname{mult}(s(n),\operatorname{fact}(n))$

$\operatorname{sub}_{1}(x)=x\dot{-}1:=\left\{\begin{array}[]{ll}0&\textrm{if }x% =0,\\ x-1&\textrm{otherwise,}\end{array}\right.$

built using $z$ and $s$ : $\operatorname{sub}_{1}(0)=z(0)$ , and $\operatorname{sub}_{1}(n+1)=s(\operatorname{sub}_{1}(n))$ ;

8.

more generally, $\operatorname{sub}_{m}(x)=x\dot{-}m$ may be defined: $\operatorname{sub}_{m}=\operatorname{sub}_{1}^{m}$ .
9.

$\operatorname{sub}(x,y)=x\dot{-}y$ : $\operatorname{sub}(x,0)=\operatorname{id}(x)$ , and $\operatorname{sub}(x,n+1)=\operatorname{sub}_{1}(\operatorname{sub}(x,n))$ .
10.

$\operatorname{diff}(x,y)=|x-y|:=\operatorname{sub}(x,y)+\operatorname{sub}(y,x)$

11.

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

built using $\operatorname{const}_{1}$ and $z$ : $d_{0}(0)=\operatorname{const}_{1}(0)$ , and $d_{0}(n+1)=z(d_{0}(n))$ .

12.

more generally,

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

is primitive recursive, for it is $d_{0}(\operatorname{diff}(x,\operatorname{const}_{m}(x))$ .

13.

even more generally,

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

where $S=\{a_{1},\ldots,a_{m}\}$ , is primitive recursive, for it is $d_{a_{1}}+\cdots+d_{a_{m}}$ .

14.

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

which is just $\operatorname{sub}(\operatorname{const}_{1}(x),d_{0}(x))$ .

15.

$\operatorname{rem}(x,y):=\left\{\begin{array}[]{ll}0&\textrm{if }y=0,\\ x\!\!\!\!\!\mod\!y&\textrm{otherwise,}\end{array}\right.$

where $x\!\!\!\mod\!y$ is the remainder of $x\div y$ . Suppose $y\neq 0$ . Then $0\!\!\!\mod\!y=0$ . In addition,

$(n+1)\!\!\!\!\mod\!y=\left\{\begin{array}[]{ll}0&\textrm{if }\operatorname{% diff}(s(n\!\!\!\!\mod\!y),y)=0,\\ s(n\!\!\!\!\mod\!y)&\textrm{otherwise,}\end{array}\right.$

Then $\operatorname{rem}(0,y)=z(y)$ , and

$\displaystyle\operatorname{rem}(n+1,y)$	$\displaystyle=$	$\displaystyle\operatorname{sgn}(y)(\operatorname{rem}(n,y)+1)\operatorname{sgn% }(\|\operatorname{rem}(n,y)+1-y\|)$
	$\displaystyle=$	$\displaystyle\operatorname{mult}(\operatorname{sgn}(y),\operatorname{mult}(s(% \operatorname{rem}(n,y)),\operatorname{sgn}(\operatorname{diff}(s(% \operatorname{rem}(n,y)),y))))$
	$\displaystyle=$	$\displaystyle g(y,\operatorname{rem}(n,y))$

where $g(y,x):=\operatorname{mult}(\operatorname{sgn}(y),\operatorname{mult}(s(x),% \operatorname{sgn}(\operatorname{diff}(s(x),y))))$ . The reason for including $\operatorname{sgn}(y)$ is to account for the case when $y=0$ .

16.

$q(x,y)=\left\{\begin{array}[]{ll}\textrm{quotient of }x\div y&\textrm{if }y% \neq 0\\ 0&\textrm{otherwise.}\end{array}\right.$

To see that $q$ is primitive recursive, we use equation

$x=yq(x,y)+\operatorname{rem}(x,y)$

obtained from the division algorithm for integers. Then

$yq(x,y)+\operatorname{rem}(x,y)+1=x+1=yq(x+1,y)+\operatorname{rem}(x+1,y).$

Simplify and we get

$y(q(x+1,y)-q(x,y))=\operatorname{rem}(x,y)+1-\operatorname{rem}(x+1,y).$

Thus, by the previous example, we get

$q(n+1,y)=\left\{\begin{array}[]{ll}q(n,y)+1&\textrm{if }\operatorname{rem}(n,y% )+1=y,\\ q(n,y)&\textrm{otherwise.}\end{array}\right.$

Therefore, $q(0,y)=z(y)$ , and

$q(n+1,y)=\operatorname{sgn}(y)(q(n,y)+\operatorname{sgn}(\operatorname{diff}(s% (\operatorname{rem}(n,y)),y)))$

where $\operatorname{sgn}(y)$ takes the case $y=0$ into account.

Remarks.

•

All of the functions above are in fact examples of elementary recursive functions.
•

Example 3(m) above is a special case of a more general phenomenon. Recall that a subset $S\subseteq\mathbb{N}^{n}$ is called primitive recursive if its characteristic function $\varphi_{S}$ is primitive recursive. If we take $S=\{m\}$ , then $\varphi_{S}=d_{m}$ . Furthermore, a predicate $\Phi(\boldsymbol{x})$ over $\mathbb{N}^{k}$ is primitive recursive if the corresponding set $S(\Phi):=\{\boldsymbol{x}\in\mathbb{N}^{k}\mid\Phi(\boldsymbol{x})\}$ is primitive recursive.
•

The technique of bounded maximization may be used to prove the primitive recursiveness of the quotient and the reminder functions in examples 3(o) and 3(p). See this entry (http://planetmath.org/BoundedMaximization) for more detail.

Title	examples of primitive recursive functions
Canonical name	ExamplesOfPrimitiveRecursiveFunctions
Date of creation	2013-03-22 19:05:06
Last modified on	2013-03-22 19:05:06
Owner	CWoo (3771)
Last modified by	CWoo (3771)
Numerical id	17
Author	CWoo (3771)
Entry type	Example
Classification	msc 03D20
Related topic	ExamplesOfPrimitiveRecursivePredicates