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:

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

    “According to our social pyramid, all men who feel displaced racially, culturally, and/or because of economic hardships will turn on those whom they feel they can order and humiliate, usually women, children, and animals—just as they have been ordered and humiliated by those privileged few who are in power. However, this definition does not explain why there are privileged men who behave this way toward women.”
    —Ana Castillo (b. 1953)

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