Relationship To Recursive Functions
The broader class of partial recursive functions is defined by introducing an unbounded search operator. The use of this operator may result in a partial function, that is, a relation with at most one value for each argument, but does not necessarily have any value for any argument (see domain). An equivalent definition states that a partial recursive function is one that can be computed by a Turing machine. A total recursive function is a partial recursive function that is defined for every input.
Every primitive recursive function is total recursive, but not all total recursive functions are primitive recursive. The Ackermann function A(m,n) is a well-known example of a total recursive function that is not primitive recursive. There is a characterization of the primitive recursive functions as a subset of the total recursive functions using the Ackermann function. This characterization states that a function is primitive recursive if and only if there is a natural number m such that the function can be computed by a Turing machine that always halts within A(m,n) or fewer steps, where n is the sum of the arguments of the primitive recursive function.
An important property of the primitive recursive functions is that they are a recursively enumerable subset of the set of all total recursive functions (which is not itself recursively enumerable). This means that there is a single computable function f(e,n) such that:
- For every primitive recursive function g, there is an e such that g(n) = f(e,n) for all n, and
- For every e, the function h(n) = f(e,n) is primitive recursive.
However, the primitive recursive functions are not the largest recursively enumerable set of total computable functions.
Read more about this topic: Primitive Recursive Function
Famous quotes containing the words relationship to, relationship and/or functions:
“Women, because of their colonial relationship to men, have to fight for their own independence. This fight for our own independence will lead to the growth and development of the revolutionary movement in this country. Only the independent woman can be truly effective in the larger revolutionary struggle.”
—Women’s Liberation Workshop, Students for a Democratic Society, Radical political/social activist organization. “Liberation of Women,” in New Left Notes (July 10, 1967)
“The relationship between mother and professional has not been a partnership in which both work together on behalf of the child, in which the expert helps the mother achieve her own goals for her child. Instead, professionals often behave as if they alone are advocates for the child; as if they are the guardians of the child’s needs; as if the mother left to her own devices will surely damage the child and only the professional can rescue him.”
—Elaine Heffner (20th century)
“Let us stop being afraid. Of our own thoughts, our own minds. Of madness, our own or others’. Stop being afraid of the mind itself, its astonishing functions and fandangos, its complications and simplifications, the wonderful operation of its machinery—more wonderful because it is not machinery at all or predictable.”
—Kate Millett (b. 1934)