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:

    There is the falsely mystical view of art that assumes a kind of supernatural inspiration, a possession by universal forces unrelated to questions of power and privilege or the artist’s relation to bread and blood. In this view, the channel of art can only become clogged and misdirected by the artist’s concern with merely temporary and local disturbances. The song is higher than the struggle.
    Adrienne Rich (b. 1929)

    Much poetry seems to be aware of its situation in time and of its relation to the metronome, the clock, and the calendar. ... The season or month is there to be felt; the day is there to be seized. Poems beginning “When” are much more numerous than those beginning “Where” of “If.” As the meter is running, the recurrent message tapped out by the passing of measured time is mortality.
    William Harmon (b. 1938)

    Financiers are great mythomaniacs, their explanations and superstitions are those of primitive men; the world is a jungle to them. They perceive acutely that they are at the dawn of economic history.
    Christina Stead (1902–1983)

    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)