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:
“The definition of good prose is proper words in their proper places; of good verse, the most proper words in their proper places. The propriety is in either case relative. The words in prose ought to express the intended meaning, and no more; if they attract attention to themselves, it is, in general, a fault.”
—Samuel Taylor Coleridge (17721834)
“Mothers often are too easily intimidated by their childrens 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)