Editing General recursive function (section)

==Definition==

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 [[μ operator|minimization operator {{mvar|μ}}]].

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 {{mvar|C{{su|b=n|p=k}}}}'': For each natural number {{mvar|n}} and every {{mvar|k}}
#::<math>C_n^k(x_1,\ldots,x_k) \ \stackrel{\mathrm{def}}{=}\  n</math>
#: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:''
#::<math>S(x) \ \stackrel{\mathrm{def}}{=}\  x + 1\,</math>
# ''Projection function'' <math>P_i^k</math> (also called the ''Identity function''): For all natural numbers <math>i, k</math> such that <math>1\le i\le k</math>:
#::<math>P_i^k(x_1,\ldots,x_k) \ \stackrel{\mathrm{def}}{=}\  x_i \, .</math>

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'' <math>\circ\,</math> (also called the ''substitution operator''): Given an m-ary function <math>h(x_1,\ldots,x_m)\,</math> and m k-ary functions <math>g_1(x_1,\ldots,x_k),\ldots,g_m(x_1,\ldots, x_k)</math>:
#::<math>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)).</math>
#:This means that <math>f(x_1,\ldots,x_k)</math> is defined only if <math>g_1(x_1,\ldots,x_k),\ldots, g_m(x_1,\ldots,x_k),</math> and <math>h(g_1(x_1,\ldots,x_k),\ldots,g_m(x_1,\ldots,x_k))</math> are all defined.
# ''Primitive recursion operator'' {{mvar|&rho;}}: Given the ''k''-ary function <math>g(x_1,\ldots,x_k)\,</math> and ''k''+2 -ary function <math>h(y,z,x_1,\ldots,x_k)\,</math>:
#::<math>\begin{align} 
             \rho(g, h) &\ \stackrel{\mathrm{def}}{=}\  f \quad\text{where the k+1 -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}</math>
#:This means that <math>f(y,x_1,\ldots,x_k)</math> is defined only if <math>g(x_1,\ldots,x_k)</math> and <math>h(z,f(z,x_1,\ldots,x_k),x_1,\ldots,x_k)</math> are defined for all <math>z<y.</math>
#''Minimization operator''  {{mvar|&mu;}}: Given a (''k''+1)-ary function <math>f(y, x_1, \ldots, x_k)\,</math>, the ''k''-ary function <math>\mu(f)</math> is defined by:
#::<math>\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}</math>
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 {{mvar|f}} is not defined, then the search never terminates, and <math> \mu(f)</math> is not defined for the argument <math>(x_1, \ldots, x_k).</math>

While some textbooks use the μ-operator as defined here,<ref name="Enderton.1972">Enderton, H. B., A Mathematical Introduction to Logic, Academic Press, 1972</ref><ref name="Boolos.Burgess.Jeffrey.2007">Boolos, G. S., Burgess, J. P., Jeffrey, R. C., Computability and Logic, Cambridge University Press, 2007</ref> others<ref name="Jones.1997">Jones, N. D., Computability and Complexity: From a Programming Perspective, The MIT Press, Cambridge, Massachusetts, London, England, 1997</ref><ref>Kfoury, A. J., R. N. Moll, and M. A. Arbib, A Programming Approach to Computability, 2nd ed., Springer-Verlag, Berlin, Heidelberg, New York, 1982</ref> demand that the μ-operator is applied to ''total'' functions {{mvar|f}} 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 [[#Normal form theorem|below]]).<ref name="Enderton.1972"/><ref name="Boolos.Burgess.Jeffrey.2007"/> 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.<ref name="Jones.1997"/>

The ''[[strong equality]]'' relation <math>\simeq</math> can be used to compare partial μ-recursive functions.  This is defined for all partial functions ''f'' and ''g'' so that
:<math>f(x_1,\ldots,x_k) \simeq g(x_1,\ldots,x_l)</math> 
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.