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:
“No man, not even a doctor, ever gives any other definition of what a nurse should be than this—”devoted and obedient.” This definition would do just as well for a porter. It might even do for a horse. It would not do for a policeman.”
—Florence Nightingale (1820–1910)
“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)
“Scientific method is the way to truth, but it affords, even in
principle, no unique definition of truth. Any so-called pragmatic
definition of truth is doomed to failure equally.”
—Willard Van Orman Quine (b. 1908)