The
μ-recursive functions (or
general 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
minimization operator. The smallest class of functions including the initial functions and closed under composition and primitive recursion (i.e. without minimisation) 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 : For each natural number and every • ::C_n^k(x_1,\ldots,x_k) \ \stackrel{\mathrm{def}}{=}\ n • :Alternative definitions use instead a
zero function as a primitive function that always returns zero, and build the constant functions from the zero function, the successor function and the
composition operator. •
Successor function S: • ::S(x) \ \stackrel{\mathrm{def}}{=}\ x + 1\, •
Projection function P_i^k (also called the
Identity function): For all natural numbers i, k such that 1\le i\le k: • ::P_i^k(x_1,\ldots,x_k) \ \stackrel{\mathrm{def}}{=}\ x_i \, . 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): •
Composition operator \circ\, (also called the
substitution operator): Given an
m-ary function h(x_1,\ldots,x_m)\, and
m k-ary functions g_1(x_1,\ldots,x_k),\ldots,g_m(x_1,\ldots, x_k): • ::h \circ (g_1, \ldots, g_m) \ \stackrel{\mathrm{def}}{=}\ f, \quad\text{where}\quad f(x_1,\ldots,x_k) = h(g_1(x_1,\ldots,x_k),\ldots,g_m(x_1,\ldots,x_k)). • :This means that f(x_1,\ldots,x_k) is defined only if g_1(x_1,\ldots,x_k),\ldots, g_m(x_1,\ldots,x_k), and h(g_1(x_1,\ldots,x_k),\ldots,g_m(x_1,\ldots,x_k)) are all defined. •
Primitive recursion operator : Given the
k-ary function g(x_1,\ldots,x_k)\, and
k+2 -ary function h(y,z,x_1,\ldots,x_k)\,: • ::\begin{align} \rho(g, h) &\ \stackrel{\mathrm{def}}{=}\ f \quad\text{where the }k+1\text{-ary function } f \text{ is defined by}\\ f(0,x_1,\ldots,x_k) &= g(x_1,\ldots,x_k) \\ f(S(y),x_1,\ldots,x_k) &= h(y,f(y,x_1,\ldots,x_k),x_1,\ldots,x_k)\,.\end{align} • :This means that f(y,x_1,\ldots,x_k) is defined only if g(x_1,\ldots,x_k) and h(z,f(z,x_1,\ldots,x_k),x_1,\ldots,x_k) are defined for all z •
Minimization operator : Given a (
k+1)-ary function f(y, x_1, \ldots, x_k)\,, the
k-ary function \mu(f) is defined by: • ::\begin{align} \mu(f)(x_1, \ldots, x_k) = z \stackrel{\mathrm{def}}{\iff}\ f(i, x_1, \ldots, x_k)&>0 \quad \text{for}\quad i=0, \ldots, z-1 \quad\text{and}\\ f(z, x_1, \ldots, x_k)&=0\quad \end{align} 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 \mu(f) is not defined for the argument (x_1, \ldots, x_k). While some textbooks use the μ-operator as defined here, others demand that the μ-operator is applied to
total functions only. 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 only difference is, that it becomes undecidable whether a specific function definition defines a μ-recursive function, as it is undecidable whether a computable (i.e. μ-recursive) function is total. The
strong equality relation \simeq can be used to compare partial μ-recursive functions. This is defined for all partial functions
f and
g so that :f(x_1,\ldots,x_k) \simeq g(x_1,\ldots,x_l) 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. ==Examples==