- Grzegorczyk hierarchy
The Grzegorczyk hierarchy, named after the Polish logician
Andrzej Grzegorczyk , is a hierarchy of sets of functions used inrecursive function theory . Every function in the Grzegorczyk hierarchy is aprimitive recursive function , and every primitive recursive function appears in the hierarchy at some level. See alsorecursive language . The hierarchy deals with the rate at which functions may grow: intuitively, functions in the low level of the hierarchy grow very slowly (for example, linearly), while functions higher up in the hierarchy grow very rapidly.Definition
First we introduce an infinite set of functions, denoted "Ei" for some natural number "i". We define E_0(x,y)=x+y and E_1(x)=x^2+2. 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 E_n(x)=E^{x}_{n-1}(2).
From these functions we define the Grzegorczyk hierarchy. mathcal{E}^0, the first set in the hierarchy, contains the following functions:
# the zero function (e.g., "f"("x") = 0);
# the successor function (e.g., "s"("x") = "x" + 1);
# the projection functions (e.g., "p"("x", "y", "z") = "x");
# the compositions of functions in the set, for example, if "g" and "h" are in mathcal{E}^0, then "f"("x") = "h"("g"("x")) is as well; and
# the results of limited recursion applied to functions in the set, for example, if "g", "h" and "j" are in mathcal{E}^0 and f(y, x)leq j(y, x) for all "x" and "y", and further f(0, x)=g(x) and f(y+1,x)=h(y,x,f(y,x)), then "f" is in mathcal{E}^0 as well.For each "n" greater than 0, we define mathcal{E}^n to be set of functions that results from repeatedly applying composition (of functions in mathcal{E}^n) and limited recursion (ibid) to the functions "E"0 and "En" together with the zero function, the successor function, and the projection functions.
Note that mathcal{E}^1 provides all addition functions, mathcal{E}^2 provides all multiplication functions, mathcal{E}^3 provides all exponentiation functions, mathcal{E}^4 provides all
tetration functions, and so on.Relationships to other function classes
The fourth level in the hierarchy, mathcal{E}^3, is exactly the elementary recursive functions.
References
* Brainerd, W.S., Landweber, L.H. (1974), "Theory of Computation", Wiley, ISBN 0-471-09585-0
* Rose, H.E., "Subrecursion: Functions and hierarchies", Oxford University Press, New York, USA, 1984. ISBN 0-19-853189-3
Wikimedia Foundation. 2010.