Primitiv-rekursive Funktionen sind Funktionen, die auf bestimmte Art aus einfachen Grundoperationen zusammengesetzt werden können. Der Begriff primitiv-rekursive Funktion wurde von der ungarischen Mathematikerin Rózsa Péter geprägt. Primitiv-rekursive Funktionen spielen in der Theoretischen Informatik eine Rolle, insbesondere in Zusammenhang mit Berechenbarkeit.

Eigenschaften

---

Primitiv-rekursive Funktionen zeichnen sich durch eine gewisse Gutartigkeit aus. Insbesondere kann man vor der Berechnung eines Funktionswertes angeben, wie komplex diese Operation ist, d. h. auch wie lange diese Berechnung dauern wird. Lange Zeit hoffte man, dass sich jede berechenbare mathematische Funktion und jedes Problem primitiv-rekursiv berechnen lässt. Diese Hoffnung wurde durch die Ackermannfunktion zerstört, die erste bekannte Funktion, die nicht primitiv-rekursiv berechenbar war.

Die Klasse $Pr$ der primitiv-rekursiven Funktionen (von $\backslash mathbb\{N\}^k\; \backslash rightarrow\; \backslash mathbb\{N\}$) umfasst zunächst die folgenden primitiv-rekursiven Grundfunktionen:

1. konstante Funktion: $f\_c^k\; \backslash left(\; n\_1,\; ...,\; n\_k\; \backslash right)\; :=\; c$, $c\; \backslash in\; \backslash mathbb\{N\}$
2. Projektion auf ein Argument: $\backslash pi\_i^k\; \backslash left(\; n\_1,\; ...,\; n\_k\; \backslash right)\; :=\; n\_i$, $1\; \backslash le\; i\; \backslash le\; k$
3. Nachfolgefunktion: $\backslash nu\; \backslash left(\; n\; \backslash right)\; :=\; n\; +\; 1$ (auch Sukzessorfunktion genannt)

Aus diesen werden mit folgenden Operationen alle weiteren primitiv-rekursiven Funktionen gewonnen:

1. Komposition: $f\; \backslash left(\; n\_1,\; ...,\; n\_k\; \backslash right)\; :=\; g\; \backslash left(\; h\_1\; \backslash left(\; n\_1,\; ...,\; n\_k\; \backslash right),\; ...,\; h\_m\; \backslash left(\; n\_1,\; ...,\; n\_k\; \backslash right)\; \backslash right)$ falls $g,\; h\_1,\; ...,\; h\_m\; \backslash in\; Pr$
2. Primitive Rekursion: $f\; \backslash left(\; 0,\; n\_2,\; ...,\; n\_k\; \backslash right)\; :=\; g\; \backslash left(\; n\_2,\; ...,\; n\_k\; \backslash right)$, $f\; \backslash left(\; n\_1\; +\; 1,\; n\_2,\; ...,\; n\_k\; \backslash right)\; :=\; h\; \backslash left(\; f\; \backslash left(\; n\_1,\; ...,\; n\_k\; \backslash right),\; n\_1,\; ...,\; n\_k\; \backslash right)$, falls $h,\; g\; \backslash in\; Pr$

Jede primitiv-rekursive Funktion ist LOOP-berechenbar (vgl. LOOP-Programm) und umgekehrt.

Beispiele

---

Es folgen einige Beispiele, wie sich bekannte Operationen als primitiv-rekursive Funktionen definieren lassen.

Vorgängerfunktion

Die Vorgängerfunktion $p(x)\; =\; x\; -\; 1$ ergibt sich durch primitive Rekursion. Als Funktion $g$ verwendet man die Nullfunktion und als Funktion $f$ die Projektion. Es ergibt sich dadurch:

$p(0)\; =\; g()\; =\; 0$

$p(n+1)\; =\; h(p(n),n)\; =\; \backslash pi\_2^2(p(n),n)\; =\; n$

Addition

Die Addition $\backslash mbox\{add\}\; \backslash left(a,b\; \backslash right)=a+b$ der Natürlichen Zahlen lässt sich wie folgt definieren:

$\backslash mbox\{add\}(0,b):=\backslash pi\_1^1(b)=b$ (Projektion)

$\backslash mbox\{add\}(n+1,b):=\backslash nu\; \backslash left(\backslash mbox\{add\}(n,b)\; \backslash right)$ (Primitive Rekursion)

Um aus der Addition eine Subtraktion zu machen ersetzt man die Nachfolgerfunktion $\backslash nu$ durch die Vorgängerfunktion $p$.

Multiplikation

Zur Definition der Multiplikation $\backslash mbox\{mult\}(a,b)=a\backslash cdot\; b$ dürfen wir die Addition schon verwenden, da diese ja, wie gerade gezeigt, primitiv-rekursiv ist:

$\backslash mbox\{mult\}(0,b):=\; f\_0^1(b)=0$ (konstante Funktion)

$\backslash mbox\{mult\}(n+1,b):=\; \backslash mbox\{add\}\backslash left(b,\backslash mbox\{mult\}(n,b)\; \backslash right)=\backslash mbox\{mult\}(n,b)+b$ (Primitive Rekursion)

Potenzieren

Zur Definition des Potenzierens $\backslash mbox\{pot\}(a,b)=a^b$ dürfen wir die Addition und Multiplikation schon verwenden, da diese ja, wie gerade gezeigt, primitiv-rekursiv sind:

$\backslash mbox\{pot\}(a,0):=\; v(0)=1$ (konstante Funktion)

$\backslash mbox\{pot\}(a,v(b)):=\; \backslash mbox\{mult\}\backslash left(\backslash mbox\{pot\}(a,b),a\; \backslash right)=$ (Primitive Rekursion)

Siehe auch: µ-Rekursion

Theoretische Informatik

Primitivně rekurzivní funkce | Primitive recursive function | Recursión primitiva | Fonction récursive primitive | PRC | Funzione ricorsiva primitiva | 原始递归函数