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.

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 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 $\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$ (auch Sukzessorfunktion genannt)

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 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)=\pi _{2}^{2}(p(n),n)=n$

Addition

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

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

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

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

Multiplikation

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

${\mbox{mult}}(0,b):=f_{0}^{2}(0,b)=0$ (konstante Funktion)

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

Siehe auch: µ-Rekursion