Definition
First we introduce an infinite set of functions, denoted Ei for some natural number i. We define and . I.e., E0 is the addition function, and E1 is a unary function which squares its argument and adds two. Then, for each n greater than 1, we define .
From these functions we define the Grzegorczyk hierarchy., the n-th set in the hierarchy, contains the following functions:
- Ek for k < n
- the zero function (Z(x) = 0);
- the successor function (S(x) = x + 1);
- the projection functions ;
- the (generalized) compositions of functions in the set (if h, g1, g2, ... and gm are in, then is as well); and
- the results of limited (primitive) recursion applied to functions in the set, (if g, h and j are in and for all t and, and further and, then f is in as well)
In other words, is the closure of set with respect to function composition and limited recursion (as defined above).
Read more about this topic: Grzegorczyk Hierarchy
Famous quotes containing the word definition:
“Mothers often are too easily intimidated by their children’s negative reactions...When the child cries or is unhappy, the mother reads this as meaning that she is a failure. This is why it is so important for a mother to know...that the process of growing up involves by definition things that her child is not going to like. Her job is not to create a bed of roses, but to help him learn how to pick his way through the thorns.”
—Elaine Heffner (20th century)
“It is very hard to give a just definition of love. The most we can say of it is this: that in the soul, it is a desire to rule; in the spirit, it is a sympathy; and in the body, it is but a hidden and subtle desire to possess—after many mysteries—what one loves.”
—François, Duc De La Rochefoucauld (1613–1680)
“Was man made stupid to see his own stupidity?
Is God by definition indifferent, beyond us all?
Is the eternal truth man’s fighting soul
Wherein the Beast ravens in its own avidity?”
—Richard Eberhart (b. 1904)