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 der primitiv-rekursiven Funktionen (von ) umfasst zunächst die folgenden primitiv-rekursiven Grundfunktionen:
- konstante Funktion: ,
- Projektion auf ein Argument: ,
- Nachfolgefunktion:
- Komposition: falls
- Primitive Rekursion: , , falls
Siehe auch: µ-Rekursion