µ-Rekursion
-rekursive Funktionen spielen in der Theoretischen Informatik eine Rolle, insbesondere in Zusammenhang mit Berechenbarkeit. Sie stellt eine Erweiterung der primitiv rekursiven Funktionen darDie Klasse der -rekursiven Funktionen (von ) umfasst:
- alle konstante Funktion: ,
- alle Projektion: ,
- die Nachfolgefunktion:
- Komposition: falls
- Primitiver Rekursion: , , falls
- Anwendung des -Operators
Definition des -Operators:
Jede -rekursive Funktion entspricht einer WHILE-Schleife (vgl. WHILE-Programm) und umgekehrt.