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:
“Whatever may be our just grievances in the southern states, it is fitting that we acknowledge that, considering their poverty and past relationship to the Negro race, they have done remarkably well for the cause of education among us. That the whole South should commit itself to the principle that the colored people have a right to be educated is an immense acquisition to the cause of popular education.”
—Fannie Barrier Williams (1855–1944)
“Some [adolescent] girls are depressed because they have lost their warm, open relationship with their parents. They have loved and been loved by people whom they now must betray to fit into peer culture. Furthermore, they are discouraged by peers from expressing sadness at the loss of family relationships—even to say they are sad is to admit weakness and dependency.”
—Mary Pipher (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)