Inmathematical logic andcomputer science, ageneral recursive function,partial recursive function, orμ-recursive function is apartial function fromnatural numbers to natural numbers that is "computable" in an intuitive sense – as well as in aformal one. If the function istotal, it is also called atotal recursive function (sometimes shortened torecursive function).^[1] Incomputability theory, it is shown that the μ-recursive functions are precisely the functions that can be computed byTuring machines^[2][4] (this is one of the theorems that supports theChurch–Turing thesis). The μ-recursive functions are closely related toprimitive recursive functions, and their inductive definition (below) builds upon that of the primitive recursive functions. However, not every total recursive function is a primitive recursive function—the most famous example is theAckermann function.

Other equivalent classes of functions are the functions oflambda calculus and the functions that can be computed byMarkov algorithms.

The subset of alltotal recursive functions with values in{0,1} is known incomputational complexity theory as thecomplexity class R.

Theμ-recursive functions (orgeneral 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 theminimization operatorμ.

The smallest class of functions including the initial functions and closed under composition and primitive recursion (i.e. without minimisation) is the class ofprimitive 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, theAckermann function can be proven to be total recursive, and to be non-primitive.

Primitive or "basic" functions:

1. Constant functionsC^k
   _n: For each natural numbern and everyk

   ${\displaystyle C_n^k(x_1,\dots ,x_k)\stackrel{\mathrm{d}\mathrm{e}\mathrm{f}}{=}n}$

   Alternative definitions use instead azero 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.

2. Successor function S:

   ${\displaystyle S(x)\stackrel{\mathrm{d}\mathrm{e}\mathrm{f}}{=}x+1}$

3. Projection function${\displaystyle P_i^k}$ (also called theIdentity function): For all natural numbers${\displaystyle i,k}$ such that${\displaystyle 1\le i\le k}$:

   ${\displaystyle P_i^k(x_1,\dots ,x_k)\stackrel{\mathrm{d}\mathrm{e}\mathrm{f}}{=}{x}_i.}$

Operators (thedomain of a function defined by an operator is the set of the values of the arguments such that everyfunction application that must be done during the computation provides a well-defined result):

1. Composition operator${\displaystyle \circ }$ (also called thesubstitution operator): Given an m-ary function${\displaystyle h(x_1,\dots ,x_m)}$ and m k-ary functions${\displaystyle g_1(x_1,\dots ,x_k),\dots ,g_m(x_1,\dots ,x_k)}$:

   ${\displaystyle h\circ (g_1,\dots ,g_m)\stackrel{\mathrm{d}\mathrm{e}\mathrm{f}}{=}f,\text{where}f(x_1,\dots ,x_k)=h(g_1(x_1,\dots ,x_k),\dots ,g_m(x_1,\dots ,x_k)).}$

   This means that${\displaystyle f(x_1,\dots ,x_k)}$ is defined only if${\displaystyle g_1(x_1,\dots ,x_k),\dots ,g_m(x_1,\dots ,x_k),}$ and${\displaystyle h(g_1(x_1,\dots ,x_k),\dots ,g_m(x_1,\dots ,x_k))}$ are all defined.

2. Primitive recursion operatorρ: Given thek-ary function${\displaystyle g(x_1,\dots ,x_k)}$ andk+2 -ary function${\displaystyle h(y,z,x_1,\dots ,x_k)}$:

   

   This means that${\displaystyle f(y,x_1,\dots ,x_k)}$ is defined only if${\displaystyle g(x_1,\dots ,x_k)}$ and${\displaystyle h(z,f(z,x_1,\dots ,x_k),x_1,\dots ,x_k)}$ are defined for all

3. Minimization operatorμ: Given a (k+1)-ary function${\displaystyle f(y,x_1,\dots ,x_k)}$, thek-ary function${\displaystyle \mu (f)}$ 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 whichf is not defined, then the search never terminates, and${\displaystyle \mu (f)}$ is not defined for the argument${\displaystyle (x_1,\dots ,x_k).}$

While some textbooks use the μ-operator as defined here,^[5][6] others^[7][8] demand that the μ-operator is applied tototal functionsf 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 (seebelow).^[5][6] 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.^[7]

Thestrong equality relation${\displaystyle \simeq }$ can be used to compare partial μ-recursive functions. This is defined for all partial functionsf andg so that

${\displaystyle f(x_1,\dots ,x_k)\simeq g(x_1,\dots ,x_l)}$

holdsif and only if for any choice of arguments either both functions are defined and their values are equal or both functions are undefined.

Examples not involving the minimization operator can be found atPrimitive recursive function#Examples.

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.

The following examples define general recursive functions that are not primitive recursive; hence they cannot avoid using the minimization operator.

A general recursive function is calledtotal recursive function if it is defined for every input, or, equivalently, if it can be computed by atotal Turing machine. There is no way to computably tell if a given general recursive function is total - seeHalting problem.

This sectionneeds expansion. You can help byadding to it.(February 2010)

In theequivalence of models of computability, a parallel is drawn betweenTuring 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).

Anormal form theorem due to Kleene says that for eachk there are primitive recursive functions${\displaystyle U(y)}$ and${\displaystyle T(y,e,x_1,\dots ,x_k)}$ such that for any μ-recursive function${\displaystyle f(x_1,\dots ,x_k)}$ withk free variables there is ane such that

${\displaystyle f(x_1,\dots ,x_k)\simeq U(\mu (T)(e,x_1,\dots ,x_k))}$.

The numbere is called anindex orGödel number for the functionf.^{[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.

Minsky observes the${\displaystyle U}$ defined above is in essence the μ-recursive equivalent of theuniversal 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. In the following the string of parameters${\displaystyle x_1,x_2,\dots ,x_n}$ is abbreviated as${\displaystyle x}$:

• Constant function: Kleene uses "${\displaystyle C_q^n(x)=q}$" and Boolos-Burgess-Jeffrey (2002) (B-B-J) use the abbreviation "${\displaystyle {\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{s}\mathrm{t}}^n(x)=n}$":

e.g.${\displaystyle C_{13}^7(r,s,t,u,v,w,x)=13}$

e.g.${\displaystyle {\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{s}\mathrm{t}}^{13}(r,s,t,u,v,w,x)=13}$

• Successor function: Kleene uses${\displaystyle x^{\prime }}$ and${\displaystyle S}$ for "Successor". As "successor" is considered to be primitive, most texts use the apostrophe as follows:

${\displaystyle S(a)=a+1;\stackrel{\mathrm{d}\mathrm{e}\mathrm{f}}{=};a^{\prime }}$, where

${\displaystyle 1\stackrel{\mathrm{d}\mathrm{e}\mathrm{f}}{=}{0}^{\prime }}$,

${\displaystyle 2\stackrel{\mathrm{d}\mathrm{e}\mathrm{f}}{=}{0}^{″}}$, etc.

• Identity function: Kleene (1952) uses${\displaystyle U_i^n}$ to indicate theidentity function over the variables${\displaystyle x_i}$; B-B-J use the identity function${\displaystyle {\mathrm{i}\mathrm{d}}_i^n}$ over the variables${\displaystyle x_1}$ to${\displaystyle x_n}$:

${\displaystyle U_i^n(x)={\mathrm{i}\mathrm{d}}_i^n(x)=x_i}$

e.g.${\displaystyle U_3^7(r,s,t,u,v,w,x)={\mathrm{i}\mathrm{d}}_3^7(r,s,t,u,v,w,x)=t}$

• Composition (Substitution) operator: Kleene uses a bold-face${\displaystyle {\mathbf{S}}_m^n}$ (not to be confused with his${\displaystyle S}$ for "successor"!). The superscript${\displaystyle m}$ refers to the${\displaystyle m^{th}}$ function${\displaystyle f_m}$, whereas the subscript${\displaystyle n}$ refers to the${\displaystyle n^{th}}$ variable${\displaystyle x_n}$:

If we are given

${\displaystyle h(x)=g(f_1(x),\dots ,f_m(x))}$

then

${\displaystyle h(x)={\mathbf{S}}_m^n(g,f_1,\dots ,f_m)}$

In a similar manner, but without the sub- and superscripts, B-B-J write:

${\displaystyle h(x^{\prime })=Cg,f_1,\dots ,f_m}$

• Primitive Recursion: Kleene uses the symbol${\displaystyle R^n(\text{base step},\text{induction step})}$ where n indicates the number of variables; B-B-J use${\displaystyle Pr(\text{base step},\text{induction step})(x)}$. Given:

• base step:${\displaystyle h(0,x)=f(x)}$
• induction step:${\displaystyle h(y+1,x)=g(y,h(y,x),x)}$

Example: primitive recursion definition of${\displaystyle a+b}$

• base step:${\displaystyle f(0,a)=a=U_1^1(a)}$U¹
  ₁(a)
• induction step:${\displaystyle f(b^{\prime },a)=(f(b,a){)}^{\prime }=g(b,f(b,a),a)=g(b,c,a)=c^{\prime }=S(U_2^3(b,c,a))}$

${\displaystyle R^2\left(U_1^1(a),;S(U_2^3(b,c,a))\right)}$

${\displaystyle Pr\left(U_1^1(a),;S(U_2^3(b,c,a))\right)}$

Example: Kleene gives an example of how to perform the recursive derivation of${\displaystyle f(b,a)=b+a}$ (notice reversal of variables${\displaystyle a}$ and${\displaystyle b}$). He starts with${\displaystyle 3}$ initial functions

1. ${\displaystyle S(a)=a^{\prime }}$
2. ${\displaystyle U_1^1(a)=a}$
3. ${\displaystyle U_2^3(b,c,a)=c}$
4. ${\displaystyle g(b,c,a)=S(U_2^3(b,c,a))=c^{\prime }}$
5. base step:${\displaystyle h(0,a)=U_1^1(a)}$

induction step:${\displaystyle h(b^{\prime },a)=g(b,h(b,a),a)}$

He arrives at:

${\displaystyle a+b=R^2\left(U_1^1,;S_1^3(S,U_2^3)\right)}$

• Fibonacci number
• McCarthy 91 function

• Recursion theory
• Recursion
• Recursion (computer science)

• Stanford Encyclopedia of Philosophy entry
• A compiler for transforming a recursive function into an equivalent Turing machine

• Computability theory
• Theory of computation

• Articles with short description
• Short description matches Wikidata
• All articles needing examples
• Articles needing examples from November 2021
• Articles to be expanded from February 2010
• All articles to be expanded