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)
“We think of religion as the symbolic expression of our highest moral ideals; we think of magic as a crude aggregate of superstitions. Religious belief seems to become mere superstitious credulity if we admit any relationship with magic. On the other hand our anthropological and ethnographical material makes it extremely difficult to separate the two fields.”
—Ernst Cassirer (1874–1945)
“Adolescents, for all their self-involvement, are emerging from the self-centeredness of childhood. Their perception of other people has more depth. They are better equipped at appreciating others’ reasons for action, or the basis of others’ emotions. But this maturity functions in a piecemeal fashion. They show more understanding of their friends, but not of their teachers.”
—Terri Apter (20th century)