Grzegorczyk hierarchy

The Grzegorczyk hierarchy, named after the Polish logician Andrzej Grzegorczyk, is a hierarchy of sets of functions used in recursive function theory. Every function in the Grzegorczyk hierarchy is a primitive recursive function, and every primitive recursive function appears in the hierarchy at some level. See also recursive 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 "E_i" for some natural number "i". We define $E\_0(x,y)=x+y$ and $E\_1(x)=x^2+2$. I.e., "E₀" is the addition function, and "E₁" 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"₀ and "E_n" 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