Relation To Primitive Recursive Functions
The definition of is the same as that of the primitive recursive functions, RP, except that recursion is limited ( for some j in ) and the functions are explicitly included in . Thus the Grzegorczyk hierarchy can be seen as a way to limit the power of primitive recursion to different levels.
It is clear from this fact that all functions in any level of the Grzegorczyk hierarchy are primitive recursive functions (i.e. ) and thus:
It can also be shown that all primitive recursive functions are in some level of the hierarchy (Rose 1984; Gakwaya 1997), thus
and the sets partition the set of primitive recursive functions, RP.
Read more about this topic: Grzegorczyk Hierarchy
Famous quotes containing the words relation to, relation, primitive and/or functions:
“Light is meaningful only in relation to darkness, and truth presupposes error. It is these mingled opposites which people our life, which make it pungent, intoxicating. We only exist in terms of this conflict, in the zone where black and white clash.”
—Louis Aragon (1897–1982)
“The whole point of Camp is to dethrone the serious. Camp is playful, anti-serious. More precisely, Camp involves a new, more complex relation to “the serious.” One can be serious about the frivolous, frivolous about the serious.”
—Susan Sontag (b. 1933)
“The mountainous region of the State of Maine stretches from near the White Mountains, northeasterly one hundred and sixty miles, to the head of the Aroostook River, and is about sixty miles wide. The wild or unsettled portion is far more extensive. So that some hours only of travel in this direction will carry the curious to the verge of a primitive forest, more interesting, perhaps, on all accounts, than they would reach by going a thousand miles westward.”
—Henry David Thoreau (1817–1862)
“The English masses are lovable: they are kind, decent, tolerant, practical and not stupid. The tragedy is that there are too many of them, and that they are aimless, having outgrown the servile functions for which they were encouraged to multiply. One day these huge crowds will have to seize power because there will be nothing else for them to do, and yet they neither demand power nor are ready to make use of it; they will learn only to be bored in a new way.”
—Cyril Connolly (1903–1974)