# characterization of primitive recursive functions of one variable

It is possible to characterize primitive recursive functions of one variable in terms of operations involving only functions of a single variable. To describe how this goes, it is useful to first define some notation.

###### Definition 1.

Define the constant function $K\colon\mathbb{N}\to\mathbb{N}$ by $K(n)=1$ for all $n$.

###### Definition 2.

Define the identity function $I\colon\mathbb{N}\to\mathbb{N}$ by $I(n)=n$ for all $n$.

###### Definition 3.

Define the excess over square function $E\colon\mathbb{N}\to\mathbb{N}$ by $E(n)=n-m^{2}$, where $m$ is the largest integer such that $m^{2}\leq n$.

###### Definition 4.

Given a function $f\colon\mathbb{N}\to\mathbb{N}$, define the function $R(f)\colon\mathbb{N}\to\mathbb{N}$ by the following conditions:

• $R(f)(0)=0$

• $R(f)(n+1)=f(R(f)(n))$ for all integers $n\geq 0$.

###### Theorem 1.

The class of primitive recursive functions of a single variable is the smallest class $X$ of functions which contains the functions $E$ and $K$ defined above and is closed under the following three operations:

1. 1.

If $f\in X$ and $g\in X$, then $f\circ g\in X$.

2. 2.

If $f\in X$, then $f+I\in X$. 11Here $f+I$ has the usual meaning of pointwise addition$(f+I)(x)=f(x)+I(x)$

3. 3.

If $f\in X$, then $R(f)\in X$.

Title characterization of primitive recursive functions of one variable CharacterizationOfPrimitiveRecursiveFunctionsOfOneVariable 2013-03-22 16:45:25 2013-03-22 16:45:25 rspuzio (6075) rspuzio (6075) 9 rspuzio (6075) Theorem msc 03D20