Eine Funktion \begin{eqnarray} f: \mathbb{N}_{0} {}^{k} \rightarrow \mathbb{N}_{0}, \: k \geq 0 \end{eqnarray} die entweder eine der Basisfunktionen ist, oder sich durch endlich viele Anwendungen des Einsetzungsschemas, des Schemas der primitiven Rekursion oder des μ-Operators, ausgehend von den Basisfunktionen, definieren läßt. Gegenüber der Definition der primitiv-rekursiven Funktionen, die eine echte Teilmenge der μ-rekursiven Funktionen darstellen, verbleibt nur noch die Definition des μ-Operators anzugeben. Sei f eine (k + 1)-stellige Funktion. Durch Anwendung des μ-Operators entsteht die folgende k-stellige Funktion g: \begin{eqnarray} g(\vec{x}) = min\{n|f(n,\vec{x})=0\} \end{eqnarray}

Sofern das Minimum nicht existiert, so ist der betreffende Funktionswert undefiniert (partielle Funktion). Der Funktionswert ist auch dann undefiniert, wenn mindestens einer der Werte \begin{eqnarray} f(0,\vec{x}),...,f(n,\vec{x}) \end{eqnarray} undefiniert ist.

Die μ-rekursiven Funktionen stellen eine von vielen äquivalenten Definitionen für den Berechenbarkeitsbegriff dar (Berechnungstheorie, Churchsche These).

Im Vergleich mit den primitiv-rekursiven Funktionen treten bei den μ-rekursiven Funktionen nicht nur gewisse partielle Funktionen hinzu, sondern auch totale Funktionen (total berechenbare Funktion) wie z. B. die Ackermann-Funktion.