Primitiv-rekursive Funktion

Primitiv-rekursive Funktionen sind totale Funktionen, die aus einfachen Grundfunktionen (konstante 0-Funktion, Projektionen auf ein Argument und Nachfolgefunktion) durch Komposition und (primitive) Rekursion gebildet werden können. Die primitive Rekursion lässt sich auf Richard Dedekinds 126. Theorem in Was sind und was sollen die Zahlen? (1888) zurückführen. Die primitiv rekursive Arithmetik geht auf Thoralf Skolem (1923) zurück. Der Begriff primitiv-rekursive Funktion wurde von der ungarischen Mathematikerin Rózsa Péter geprägt. Primitiv-rekursive Funktionen spielen in der Rekursionstheorie, einem Teilgebiet der theoretischen Informatik, eine Rolle. Sie treten im Zusammenhang mit der Explikation des Berechenbarkeitsbegriffs auf.

Alle primitiv-rekursiven Funktionen sind im intuitiven Sinn berechenbar. Sie schöpfen aber nicht alle intuitiv berechenbaren Funktionen aus, Beispiele dafür sind die Ackermannfunktion und die Sudanfunktion, welche beide berechenbar, aber nicht primitiv-rekursiv sind. Eine vollständige Erfassung des Berechenbarkeitsbegriffs gelingt erst durch die µ-rekursiven Funktionen.

Für primitiv-rekursive Funktionen ist es möglich, ein Komplexitätsmaß zu definieren, d. h., es kann die Dauer der Berechnung eines ihrer Funktionswerte vorab ermittelt werden.

Die Klasse der primitiv-rekursiven Funktionen und die der LOOP-berechenbaren (vgl. LOOP-Programm) Funktionen sind äquivalent.