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:
“... the Wall became a magnet for citizens of every generation, class, race, and relationship to the war perhaps because it is the only great public monument that allows the anesthetized holes in the heart to fill with a truly national grief.”
—Adrienne Rich (b. 1929)
“Harvey: Oh, you kids these days, I’m telling you. You think the only relationship a man and a woman can have is a romantic one.
Gil: That sure is what we think. You got something better?
Harvey: Oh, romance is very nice. A good thing for youngsters like you, but Helene and I have found something we think is more appropriate to our stage of life—companionship.
Gil: Companionship? I’ve got a flea-bitten old hound at home who’ll give me that.”
—Tom Waldman (d. 1985)
“One of the most highly valued functions of used parents these days is to be the villains of their children’s lives, the people the child blames for any shortcomings or disappointments. But if your identity comes from your parents’ failings, then you remain forever a member of the child generation, stuck and unable to move on to an adulthood in which you identify yourself in terms of what you do, not what has been done to you.”
—Frank Pittman (20th century)