They are the smallest class of partial functions that includes the initial functions and is closed under composition, primitive recursion, and the minimization operator μ.
For example, the Ackermann function can be proven to be total recursive, and to be non-primitive.
Primitive or "basic" functions: Operators (the domain of a function defined by an operator is the set of the values of the arguments such that every function application that must be done during the computation provides a well-defined result): Intuitively, minimisation seeks—beginning the search from 0 and proceeding upwards—the smallest argument that causes the function to return zero; if there is no such argument, or if one encounters an argument for which f is not defined, then the search never terminates, and
Although this restricts the μ-operator as compared to the definition given here, the class of μ-recursive functions remains the same, which follows from Kleene's Normal Form Theorem (see below).
The following examples are intended just to demonstrate the use of the minimization operator; they could also be defined without it, albeit in a more complicated way, since they are all primitive recursive.
A general recursive function is called total recursive function if it is defined for every input, or, equivalently, if it can be computed by a total Turing machine.
There is no way to computably tell if a given general recursive function is total - see Halting problem.
In the equivalence of models of computability, a parallel is drawn between Turing machines that do not terminate for certain inputs and an undefined result for that input in the corresponding partial recursive function.
The unbounded search operator is not definable by the rules of primitive recursion as those do not provide a mechanism for "infinite loops" (undefined values).
A normal form theorem due to Kleene says that for each k there are primitive recursive functions
with k free variables there is an e such that The number e is called an index or Gödel number for the function f.[10]: 52–53 A consequence of this result is that any μ-recursive function can be defined using a single instance of the μ operator applied to a (total) primitive recursive function.
defined above is in essence the μ-recursive equivalent of the universal Turing machine: To construct U is to write down the definition of a general-recursive function U(n, x) that correctly interprets the number n and computes the appropriate function of x. to construct U directly would involve essentially the same amount of effort, and essentially the same ideas, as we have invested in constructing the universal Turing machine [11]A number of different symbolisms are used in the literature.
An advantage to using the symbolism is a derivation of a function by "nesting" of the operators one inside the other is easier to write in a compact form.