General recursive function
In mathematical logic and computer science, a general recursive function, partial recursive function, or
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} is known in computational complexity theory as the complexity class R.
Definition
[edit]The
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 Ck
n: For each natural number n and every k- 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:
- Projection function (also called the Identity function): For all natural numbers such that :
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 (also called the substitution operator): Given an m-ary function and m k-ary functions :
- This means that is defined only if and are all defined.
- Primitive recursion operator
ρ : Given the k-ary function and k+2 -ary function :- This means that is defined only if and are defined for all
- Minimization operator
μ : Given a (k+1)-ary function , the k-ary function 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 which f is not defined, then the search never terminates, and is not defined for the argument
While some textbooks use the
The strong equality operator can be used to compare partial
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
[edit]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 integer square root of x can be defined as the least z such that . Using the minimization operator, a general recursive definition is , where Not, Gt, and Mul are logical negation, greater-than, and multiplication,[9] respectively. In fact, is 0 if, and only if, holds. Hence is the least z such that holds. The negation junctor Not is needed since Gt encodes truth by 1, while
μ seeks for 0.
The following examples define general recursive functions that are not primitive recursive; hence they cannot avoid using the minimization operator.
Total recursive function
[edit]A general recursive function is called total recursive function if it is defined for every input, or, equivalently, if it can be computed by a total Turing machine. There is no way to computably tell if a given general recursive function is total - see Halting problem.
Equivalence with other models of computability
[edit]![]() | This section needs expansion. You can help by adding to it. (February 2010) |
In the equivalence of models of computability, a parallel is drawn between Turing 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).
Normal form theorem
[edit]A normal form theorem due to Kleene says that for each k there are primitive recursive functions and such that for any
- .
The number e is called an index or Gödel number for the function f.[10]: 52–53 A consequence of this result is that any
Minsky observes the defined above is in essence the
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]
Symbolism
[edit]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 x1, ..., xn is abbreviated as x:
- Constant function: Kleene uses " Cn
q(x) = q " and Boolos-Burgess-Jeffrey (2002) (B-B-J) use the abbreviation " constn( x) = n ":
- e.g. C7
13 ( r, s, t, u, v, w, x ) = 13 - e.g. const13 ( r, s, t, u, v, w, x ) = 13
- e.g. C7
- 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 =def a', where 1 =def 0', 2 =def 0 ' ', etc.
- Identity function: Kleene (1952) uses " Un
i " to indicate the identity function over the variables xi; B-B-J use the identity function idn
i over the variables x1 to xn:
- Un
i( x ) = idn
i( x ) = xi - e.g. U7
3 = id7
3 ( r, s, t, u, v, w, x ) = t
- Composition (Substitution) operator: Kleene uses a bold-face Sm
n (not to be confused with his S for "successor" ! ). The superscript "m" refers to the mth of function "fm", whereas the subscript "n" refers to the nth variable "xn":
- If we are given h( x )= g( f1(x), ... , fm(x) )
- h(x) = Sn
m(g, f1, ... , fm )
- h(x) = Sn
- In a similar manner, but without the sub- and superscripts, B-B-J write:
- h(x')= Cn[g, f1 ,..., fm](x)
- Primitive Recursion: Kleene uses the symbol " Rn(base step, induction step) " where n indicates the number of variables, B-B-J use " Pr(base step, induction step)(x)". Given:
- base step: h( 0, x )= f( x ), and
- 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 = U1
1(a) - induction step: f( b' , a ) = ( f ( b, a ) )' = g( b, f( b, a), a ) = g( b, c, a ) = c' = S(U3
2( b, c, a ))
- R2 { U1
1(a), S [ (U3
2( b, c, a ) ] } - Pr{ U1
1(a), S[ (U3
2( b, c, a ) ] }
- base step: f( 0, a ) = a = U1
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'
- U1
1(a) = a - U3
2( b, c, a ) = c - g(b, c, a) = S(U3
2( b, c, a )) = c' - base step: h( 0, a ) = U1
1(a)
- induction step: h( b', a ) = g( b, h( b, a ), a )
He arrives at:
- a+b = R2[ U1
1, S3
1(S, U3
2) ]
- a+b = R2[ U1
Examples
[edit]See also
[edit]References
[edit]- ^ "Recursive Functions". The Stanford Encyclopedia of Philosophy. Metaphysics Research Lab, Stanford University. 2021.
- ^ Stanford Encyclopedia of Philosophy, Entry Recursive Functions, Sect.1.7: "[The class of
μ -recursive functions] turns out to coincide with the class of the Turing-computable functions introduced by Alan Turing as well as with the class of theλ -definable functions introduced by Alonzo Church." - ^ Kleene, Stephen C. (1936). "
λ -definability and recursiveness". Duke Mathematical Journal. 2 (2): 340–352. doi:10.1215/s0012-7094-36-00227-2. - ^ 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: [3] - ^ a b Enderton, H. B., A Mathematical Introduction to Logic, Academic Press, 1972
- ^ a b Boolos, G. S., Burgess, J. P., Jeffrey, R. C., Computability and Logic, Cambridge University Press, 2007
- ^ a b 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#Junctors, Primitive recursive function#Equality predicate, and Primitive recursive function#Multiplication
- ^ Stephen Cole Kleene (Jan 1943). "Recursive predicates and quantifiers" (PDF). Transactions of the American Mathematical Society. 53 (1): 41–73. doi:10.1090/S0002-9947-1943-0007371-8.
- ^ Minsky 1972, pp. 189.
- Kleene, Stephen (1991) [1952]. Introduction to Metamathematics. Walters-Noordhoff & North-Holland. ISBN 0-7204-2103-9.
- Soare, R. (1999) [1987]. Recursively enumerable sets and degrees: A Study of Computable Functions and Computably Generated Sets. Springer-Verlag. ISBN 9783540152996.
- Minsky, Marvin L. (1972) [1967]. Computation: Finite and Infinite Machines. Prentice-Hall. pp. 210–5. ISBN 9780131654495.
- On pages 210-215 Minsky shows how to create the
μ -operator using the register machine model, thus demonstrating its equivalence to the general recursive functions.
- Boolos, George; Burgess, John; Jeffrey, Richard (2002). "6.2 Minimization". Computability and Logic (4th ed.). Cambridge University Press. pp. 70–71. ISBN 9780521007580.