General recursive function
≈ 9 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
In mathematical logic and computer science, a general recursive function, partial recursive function, or μ-recursive function is a partial function from natural numbers to natural numbers that is "computable" in an intuitive sense – as well as in a formal one. If the function is total, it is also called a total recursive function (sometimes shortened to recursive function).
In computability theory, it is shown that the μ-recursive functions are precisely the functions that can be computed by Turing machines (this is one of the theorems that supports the Church–Turing thesis). The μ-recursive functions are closely related to primitive 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 the Ackermann function.
Other equivalent classes of functions are the functions of lambda calculus and the functions that can be computed by Markov algorithms. The subset of all total recursive functions with values in is known in computational complexity theory as the complexity class R.
In mathematical logic and computer science, a general recursive function, partial recursive function, or μ-recursive function is a partial function from natural numbers to natural numbers that is "computable" in an intuitive sense – as well as in a formal one. If the function is total, it is also called a total recursive function (sometimes shortened to recursive function).
In computability theory, it is shown that the μ-recursive functions are precisely the functions that can be computed by Turing machines (this is one of the theorems that supports the Church–Turing thesis). The μ-recursive functions are closely related to primitive 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 the Ackermann function.
Other equivalent classes of functions are the functions of lambda calculus and the functions that can be computed by Markov algorithms. The subset of all total recursive functions with values in is known in computational complexity theory as the complexity class R.
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 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
Examples not involving the minimization operator can be found at Primitive 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.
Constant function: Kleene uses " C^n_q(x) = q " and Boolos-Burgess-Jeffrey (2002) (B-B-J) use the abbreviation " \mathrm{const}^n(x) = n ": e.g. C^{7}_{13}(r, s, t, u, v, w, x) = 13 e.g. \mathrm{const}^{13}(r, s, t, u, v, w, x) = 13 Successor function: Kleene uses x' and S for "Successor". As "successor" is considered to be primitive, most texts use the apostrophe as follows: S(a) = a + 1 ;\overset{\mathrm{def}}{=}; a' , where 1 \overset{\mathrm{def}}{=} 0' , 2 \overset{\mathrm{def}}{=} 0 , etc.
Identity function: Kleene (1952) uses U^n_i to indicate the identity function over the variables x_i ; B-B-J use the identity function \mathrm{id}^n_i over the variables x_1 to x_n : U^n_i(x) = \mathrm{id}^n_i(x) = x_i e.g. U^7_3(r, s, t, u, v, w, x) = \mathrm{id}^7_3(r,s,t,u,v,w,x) = t Composition (Substitution) operator: Kleene uses a bold-face \mathbf{S}^n_m (not to be confused with his S for "successor"!).
The superscript m refers to the m^{th} function f_m , whereas the subscript n refers to the n^{th} variable x_n : If we are given h(x) = g(f_1(x), \ldots, f_m(x)) then h(x) = \mathbf{S}^n_m(g, f_1, \ldots, f_m) In a similar manner, but without the sub- and superscripts, B-B-J write: h(x') = Cg, f_1, \ldots, f_m Primitive Recursion: Kleene uses the symbol R^n(\text{base step}, \text{induction step}) where n indicates the number of variables; B-B-J use \Pr(\text{base step}, \text{induction step})(x) .
Given: base step: h(0, x) = f(x) induction step: h(y+1, x) = g(y, h(y,x), x) Example: primitive recursion definition of a + b base step: f(0, a) = a = U^1_1(a) U (a) induction step: f(b', a) = (f(b, a))' = g(b, f(b,a), a) = g(b, c, a) = c' = S(U^3_2(b, c, a)) R^2\left( U^1_1(a),; S(U^3_2(b, c, a)) \right) \Pr\left( U^1_1(a),; S(U^3_2(b, c, a)) \right) Example: Kleene gives an example of how to perform the recursive derivation of f(b,a) = b + a (notice reversal of variables a and b ).
He starts with 3 initial functions S(a) = a' U^1_1(a) = a U^3_2(b, c, a) = c g(b, c, a) = S(U^3_2(b, c, a)) = c' base step: h(0, a) = U^1_1(a) induction step: h(b', a) = g(b, h(b,a), a) He arrives at: a + b = R^2\left( U^1_1,; S^3_1(S, U^3_2) \right)
Fibonacci number McCarthy 91 function
See also
Recursion theory Recursion Recursion (computer science)
External links
Stanford Encyclopedia of Philosophy entry A compiler for transforming a recursive function into an equivalent Turing machine ru:Рекурсивная функция (теория вычислимости)#Частично рекурсивная функция
Text derived from https://en.wikipedia.org/w/index.php?oldid=1341341223 under CC BY-SA 4.0; modifications have been made.