The μ-recursive functions are partial functions that take finite tuples of natural numbers and return a single natural number. They are the smallest class of partial functions that includes the initial functions and is closed under composition, primitive recursion, and the μ operator. The smallest class of functions including the initial functions and closed under composition and primitive recursion is the class of primitive recursive functions. While all primitive recursive functions are total, this is not true of partial recursive functions; for example, the minimisation of the successor function is undefined. The primitive recursive functions are a subset of the total recursive functions, which are a subset of the partial recursive functions. For example, the Ackermann function can be proven to be total recursive, and to be non-primitive. Primitive or "basic" functions:
Constant functions C: For each natural number and every
Alternative definitions use instead a zero function as a primitive function that always returns zero, and built the constant functions from the zero function, the successor function and the composition operator.
Projection function : For all natural numbers such that :
Operators :
Composition operator : Given an m-ary function and m k-ary functions :
This means that is defined only if and are all defined.
Primitive recursion operator : Given the k-ary function and k+2 -ary function :
This means that is defined only if and are defined for all
Minimization operator : Given a -ary function, the k-ary function is defined by:
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 is not defined, then the search never terminates, and is not defined for the argument whether a computable The strong equality operator can be used to compare partial μ-recursive functions. This is defined for all partial functions f and g so that holds if and only if for any choice of arguments either both functions are defined and their values are equal or both functions are undefined.
Equivalence with other models of computability
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".
A normal form theorem due to Kleene says that for each k there are primitive recursive functions and such that for any μ-recursive function with kfree variables there is an e such that The number e is called an index or Gödel number for the function f. A consequence of this result is that any μ-recursive function can be defined using a single instance of the μ operator applied to a primitive recursive function. Minsky observes that the U defined above is in essence the μ-recursive equivalent of the universal Turing machine:
Symbolism
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. In the following we will abbreviate the string of parameters x1,..., xn as x:
Constant function: Kleene uses " C = q " and Boolos-Burgess-Jeffrey use the abbreviation " constn = n ":
Successor function: Kleene uses x' and S for "Successor". As "successor" is considered to be primitive, most texts use the apostrophe as follows:
Identity function: Kleene uses " U " to indicate the identity function over the variables xi; B-B-J use the identity function id over the variables x1 to xn:
Composition operator: Kleene uses a bold-face S. The superscript "m" refers to the mth of function "fm", whereas the subscript "n" refers to the nth variable "xn":
Primitive Recursion: Kleene uses the symbol " Rn " where n indicates the number of variables, B-B-J use " Pr". Given:
Example: Kleene gives an example of how to perform the recursive derivation of f = b + a. He starts with 3 initial functions He arrives at:
