Primitive Rekursion

Die Klasse der primitiv-rekursiven Funktionen ist die kleinste Klasse von Funktionen die

1. folgende Grundfunktionen enthält:
   1. alle konstanten Funktionen $f:{\mathbb{N}}^k\to \mathbb{N}$ mit $f(x_1,\dots ,x_k)=c$
   2. die Nachfolgerfunktion $succ:\mathbb{N}\to \mathbb{N}$ mit $succ(n)=n+1$
   3. die Projektionen ${\pi }_i^k:{\mathbb{N}}^k\to \mathbb{N}$ mit ${\pi }_i^k(x_1,\dots ,x_k)=x_i$
2. und abgeschlossen ist unter folgenden Operationen:
   1. Komposition von $g_1,\dots ,g_m:{\mathbb{N}}^k\to \mathbb{N}$ und $h:{\mathbb{N}}^m\to \mathbb{N}$:
      $f:{\mathbb{N}}^k\to \mathbb{N}$ mit $f=h\circ (g_1,\dots ,g_m)$ d.h.
      $f(x_1,\dots ,x_k)=h(g_1(x_1,\dots ,x_k),\dots ,g_m(x_1,\dots ,x_k))$
   2. primitive Rekursion mit $g:{\mathbb{N}}^k\to \mathbb{N}$ und $h:{\mathbb{N}}^{k+2}\to \mathbb{N}$:
      $f:{\mathbb{N}}^{k+1}\to \mathbb{N}$ mit $f=pr(h,g)$ d.h.
      $f(0,x_1,\dots ,x_k)=g(x_1,\dots ,x_k)$
      $f(n+1,x_1,\dots ,x_k)=h(n,f(n,x_1,\dots ,x_k),x_1,\dots ,x_k)$