Grzegorczyk Hierarchy - Definition

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:

  1. Ek for k < n
  2. the zero function (Z(x) = 0);
  3. the successor function (S(x) = x + 1);
  4. the projection functions ;
  5. the (generalized) compositions of functions in the set (if h, g1, g2, ... and gm are in, then is as well); and
  6. 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 (1772–1834)

    “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)