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 {0,1} (that is, solving decision problems) is known in computational complexity theory as the complexity class R.
C
n: For each natural number Cnk(x1,…,xk) =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:
- i,k such that ∘ (also called the substitution operator): Given an m-ary function h∘(g1,…,gm) =def f,wheref(x1,…,xk)=h(g1(x1,…,xk),…,gm(x1,…,xk)).
- This means that h(g1(x1,…,xk),…,gm(x1,…,xk)) are all defined.
Primitive recursion operator h(y,z,x1,…,xk):
- g(x1,…,xk) and μ: Given a (k+1)-ary function μ(f)(x1,…,xk)=z⟺def f(i,x1,…,xk)>0fori=0,…,z−1andf(z,x1,…,xk)=0
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 (x1,…,xk).
While some textbooks use the μ-operator as defined here, others demand that the μ-operator is applied to total functions f(x1,…,xk)≃g(x1,…,xl)
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 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.
(z+1)^2 > x</math>. Using the minimization operator, a general recursive definition is <math>\\operatorname{Isqrt} = \\mu(\\operatorname{Not} \\circ \\operatorname{Gt} \\circ (\\operatorname{Mul} \\circ (S \\circ P_1^2,S \\circ P_1^2), P_2^2))</math>, where {{math|Not}}, {{math|Gt}}, and {{math|Mul}} are [[logical negation]], greater-than, and multiplication,<ref>defined in [[Primitive recursive function#Connectives]], [[Primitive recursive function#Equality predicate]], and [[Primitive recursive function#Multiplication]]</ref> respectively. In fact, <math>(\\operatorname{Not} \\circ \\operatorname{Gt} \\circ (\\operatorname{Mul} \\circ (S \\circ P_1^2,S \\circ P_1^2), P_2^2)) \\; (z,x) = (\\lnot S(z)*S(z) > x)</math> is {{val|0}} if, and only if, <math>S(z)*S(z) > x</math> holds. Hence <math>\\operatorname{Isqrt}(x)</math> is the least {{mvar|z}} such that <math>S(z)*S(z) > x</math> holds. The negation [[logical connective|connective]] {{math|Not}} is needed since {{math|Gt}} encodes truth by {{val|1}}, while {{mvar|μ}} seeks for {{val|0}}.\n"}},"i":0}}]}'>
- The integer square root of (z+1)2>x. Using the minimization operator, a general recursive definition is Gt, and S(z)∗S(z)>x holds. Hence S(z)∗S(z)>x holds. The negation connective μ seeks for 0.
The following examples define general recursive functions that are not primitive recursive; hence they cannot avoid using the minimization operator.
U(y) and f(x1,…,xk)≃U(μ(T)(e,x1,…,xk)).
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 (total) primitive recursive function.
Minsky observes the x:
- Constant function: Kleene uses "C137(r,s,t,u,v,w,x)=13
- e.g. S for "Successor". As "successor" is considered to be primitive, most texts use the apostrophe as follows:
- 2=def0″, etc.
- Identity function: Kleene (1952) uses idin over the variables Uin(x)=idin(x)=xi
- e.g. S for "successor"!). The superscript fm, whereas the subscript xn:
- If we are given
- h(x′)=Cg,f1,…,fm
- Primitive Recursion: Kleene uses the symbol h(0,x)=f(x)
- induction step: f(0,a)=a=U11(a)UR2(U11(a),;S(U23(b,c,a)))
- a and S(a)=a′
- g(b,c,a)=S(U23(b,c,a))=c′
- base step: a+b=R2(U11,;S13(S,U23))
Turing, Alan Mathison (Dec 1937). "Computability and λ-Definability".
Journal of Symbolic Logic.
2 (4):
153–163.
doi:
10.2307/2268280.
JSTOR 2268280.
S2CID 2317046. Proof outline on p.153: λ-K-definable ⟹161 λ-definable
- 1 2 Enderton, H. B., A Mathematical Introduction to Logic, Academic Press, 1972
- 1 2 Boolos, G. S., Burgess, J. P., Jeffrey, R. C., Computability and Logic, Cambridge University Press, 2007
- 1 2 Jones, N. D., Computability and Complexity: From a Programming Perspective, The MIT Press, Cambridge, Massachusetts, London, England, 1997
- ↑ Kfoury, A. J., R. N. Moll, and M. A. Arbib, A Programming Approach to Computability, 2nd ed., Springer-Verlag, Berlin, Heidelberg, New York, 1982
- ↑ defined in Primitive recursive function#Connectives, Primitive recursive function#Equality predicate, and Primitive recursive function#Multiplication
- ↑