Recursive functions may be defined more rigorously as the smallest class of partial functions from satisfying the following six criteria:
The constant function defined by for all is a recursive function.
The projection functions with defined as are recursive functions.
(Closure under primitive recursion) If and are recursive function, then , defined by the recursion
with the initial condition
is a recursive function.
(Closure under minimization) If is a recursive function then is a recursive function, where
is defined to be , if there exists a such that
are all defined,
when , and
is undefined otherwise.
The operation whereby was constructed from and in criterion 5 is known as primitive recursion. The operation described in criterion 6 is known as minimization. That is to say, for any given function , the partial function constructed as in criterion 6 is known as the minimization of and is denoted by .
The smallest set of functions satisfying criteria 1-5, but not criterion 6, is known as the set of primitive recursive functions. Therefore, the set of all recursive function is the closure of the set of primitive recursive function with respect to minimization. It can be shown that is exactly the set of Turing-computable functions. In terms of programming languages, a function is recursive iff it can be computed by a program involving the DO WHILE loops (minimization).
With some work, it can be shown that the class of recursive functions can be characterized by considerably weaker sets of criteria than those given above. See the entry “alternative characterizations of recursive functions (http://planetmath.org/AlternativeCharacterizationsOfRecursiveFunctions)” for several such characterizations.
|Date of creation||2013-03-22 14:34:35|
|Last modified on||2013-03-22 14:34:35|
|Last modified by||rspuzio (6075)|