Die Rekursionstheorie ist die Theorie des absolut Berechenbaren. Sie wurde durch GÖDEL, CHURCH, KLEENE, TURING und POST begründet und führt mit relativ kurzen Schlüssen zu weitreichenden Einsichten.
Ein rekursiver Algorithmus enthält zunächst noch ungelöste Probleme, zu deren Lösung man denselben Algorithmus nochmals anwenden muss.
Ein rekursiver Algorithmus liegt also dann vor, wenn in einer elementaren Anweisung ein Verweis auf den eigenen Algorithmus erfolgt. (Man sagt auch: "der Algorithmus ruft sich selbst auf")
GÖDEL definiert eine rekursive Funktion so:
Eine Funktion ist rekursiv, wenn sie eine Ausgangsfunktion ist oder sich aus solchen in endliche vielen Schritten durch Anwendung der angegebenen Operationen erzeugen lässt.
Anfangsfunktionen sind:
- Argumentenauswahlfunktionen (Idenditäten)
- Konstante Funktionen
- Nachfolgerfunktionen \( (∀ n∈⊆ \; n^{\boxed{ }} = n + 1) \)
Operationen mit Funktionen sind:
- Verkettung von Funktionen
- Erzeugung von Funktionen durch primitive Rekursion
- Erzeugung von Funktionen durch (beschränkte) Minimumbildung.