# examples of primitive recursive functions

1. 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. 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. 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. 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. 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. 6.

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

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

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

9. 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. 10.

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

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

Title examples of primitive recursive functions ExamplesOfPrimitiveRecursiveFunctions 2013-03-22 19:05:06 2013-03-22 19:05:06 CWoo (3771) CWoo (3771) 17 CWoo (3771) Example msc 03D20 ExamplesOfPrimitiveRecursivePredicates