You are here
Homecharacterization of primitive recursive functions of one variable
Primary tabs
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)=nm^{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. If $f\in X$ and $g\in X$, then $f\circ g\in X$.
2. If $f\in X$, then $f+I\in X$. ^{1}^{1}Here $f+I$ has the usual meaning of pointwise addition — $(f+I)(x)=f(x)+I(x)$
3. If $f\in X$, then $R(f)\in X$.
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