Primitiv-rekursive Funktion

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.

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 mathematische Funktion und jedes Problem primitiv-rekursiv berechnen lässt. Diese Hoffnung wurde durch die Ackermann-Funktion zerstört, die erste bekannte Fuktion, die nicht primitiv-rekursiv berechenbar war.

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

1. konstante Funktion: $f_{c}^{k}\left(n_{1},...,n_{k}\right):=c$, $c\in \mathbb {N}$
2. Projektion auf ein Argument: $\pi _{i}^{k}\left(n_{1},...,n_{k}\right):=n_{i}$, $1\leq i\leq k$
3. Nachfolgefunktion: $\nu \left(n\right):=n+1$

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

1. Komposition: $f\left(n_{1},...,n_{k}\right):=g\left(h_{1}\left(n_{1},...,n_{k}\right),...,h_{m}\left(n_{1},...,n_{k}\right)\right)$ falls $g,h_{1},...,h_{m}\in Pr$
2. Primitive Rekursion: $f\left(0,n_{2},...,n_{k}\right):=g\left(n_{2},...,n_{k}\right)$, $f\left(n_{1}+1,n_{2},...,n_{k}\right):=h\left(f\left(n_{1},...,n_{k}\right),n_{1},...,n_{k}\right)$, falls $h,g\in Pr$

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

Beispiele

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

Addition

Die Addition $f(a,b)=a+b$ der Natürlichen Zahlen lässt sich wie folgt definieren:

$f(0,b):=f_{b}^{2}(0,b)=b$ (konstante Funktion)

$f(n+1,b):=\nu (f(n,b))$ (Primitive Rekursion)

Multiplikation

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

$g(0,b):=f_{0}^{2}(0,b)=0$ (konstante Funktion)

$g(n+1,b):=f(g(n,b),b)=g(n,b)+b$ (Primitive Rekursion)

Siehe auch: µ-Rekursion