eine Funktion f: ℕ₀^k → ℕ₀, k ≥ 0, die entweder eine der Basisfunktionen ist, oder sich durch endlich viele Anwendungen des Einsetzungsschemas und des Schemas der primitiven Rekursion, ausgehend von den Basisfunktionen, definieren läßt.

Die Basisfunktionen bestehen aus allen Konstanten (also null-stelligen Funktionen), allen Projektionsfunktionen \begin{eqnarray}{\pi }_{i}^{k}:{{\mathbb{N}}}_{0}^{k}\to {{\mathbb{N}}}_{0},\text{}{\pi }_{i}^{k}({x}_{1},\ldots, {x}_{k})={x}_{i},\end{eqnarray}

und der einstelligen Nachfolgerfunktion N(x) = x + 1.

Das Einsetzungsschema erzeugt aus einer n-stelligen Funktion f und den k-stelligen Funktionen g₁, …, g_n eine k-stellige Funktion h: \begin{eqnarray}h(\overrightarrow{x})=f({g}_{1}(\overrightarrow{x}),\ldots, {g}_{n}(\overrightarrow{x}))\end{eqnarray}

Das Schema der primitiven Rekursion erzeugt aus einer k-stelligen Funktion g und einer (k + 2)-stelligen Funktion h eine (k + 1)-stellige Funktion f, die durch folgendes Gleichungssystem eindeutig definiert wird: \begin{eqnarray}\begin{array}{lll}f(0,\overrightarrow{x}) & = & g(\overrightarrow{x}),\\ f(n+1,\overrightarrow{x}) & = & h(n,f(n,\overrightarrow{x}),\overrightarrow{x}).\end{array}\end{eqnarray}

Ein Beispiel: Die Additionsfunktion \begin{eqnarray}s:{{\mathbb{N}}}_{0}^{2}\to {{\mathbb{N}}}_{0},\text{}s(x,y)=x+y,\end{eqnarray}

ist primitiv-rekursiv, denn s kann über das Schema der primitiven Rekursion definiert werden: \begin{eqnarray}\begin{array}{lll}s(0,y) & = & {\pi }_{1}^{1}(y),\\ s(n+1,y) & = & h(n,s(n,y),y).\end{array}\end{eqnarray}

Hierbei wird die 3-stellige Funktion h durch Anwendung des Einsetzungsschemas aus den Basisfunktionen \({\pi }_{2}^{3}\) und N gewonnen: \begin{eqnarray}h(a,b,c)=N({\pi }_{2}^{3}(a,b,c)).\end{eqnarray}

Die primitiv-rekursiven Funktionen stimmen mit den LOOP-berechenbaren Funktionen überein und bilden eine echte Teilmenge der total berechenbaren Funktionen (Ackermann-Funktion).