Grzegorczyk Hierarchy - Relation To Primitive Recursive Functions

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:

    To be a good enough parent one must be able to feel secure in one’s parenthood, and one’s relation to one’s child...The security of the parent about being a parent will eventually become the source of the child’s feeling secure about himself.
    Bruno Bettelheim (20th century)

    The foregoing generations beheld God and nature face to face; we, through their eyes. Why should not we also enjoy an original relation to the universe? Why should not we have a poetry and philosophy of insight and not of tradition, and a religion by revelation to us, and not the history of theirs?
    Ralph Waldo Emerson (1803–1882)

    An Englishman, methinks,—not to speak of other European nations,—habitually regards himself merely as a constituent part of the English nation; he is a member of the royal regiment of Englishmen, and is proud of his company, as he has reason to be proud of it. But an American—one who has made tolerable use of his opportunities—cares, comparatively, little about such things, and is advantageously nearer to the primitive and the ultimate condition of man in these respects.
    Henry David Thoreau (1817–1862)

    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)