Grzegorczyk hierarchy

The Grzegorczyk hierarchy is a hierarchy of sets of functions used in recursive function theory. Every function in the Grzegorczyk hierarchy is recursive. 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_{n-1}^{x}(2)$.

From these functions we define the Grzegorczyk hierarchy. ${\mathcal {E}}^{0}$, the first set in the hierarchy, contains the following functions:

1. The zero functions (e.g., f() = 0);
2. The successor functions (e.g., s(x) = x + 1);
3. Projection functions, which ignore arguments (e.g., p(x, y, z) = x);
4. Compositions of functions. E.g., if g and h are in ${\mathcal {E}}^{0}$, then f(x) = h(g(x)) is as well;
5. Limited recursion. If j is in ${\mathcal {E}}^{0}$ and f(x) < j(x) for all x, then f is in ${\mathcal {E}}^{0}$ as well.

For each n greater than 0, we define ${\mathcal {E}}^{n}$ to be the zero functions, the successor functions, the projection functions, the composition functions (composing over functions in ${\mathcal {E}}^{n}$), the limited recursion functions (ibid), as well as the functions E₀ and E_n

Note that ${\mathcal {E}}^{1}$ provides all addition functions, ${\mathcal {E}}^{2}$ provides all multiplication functions, ${\mathcal {E}}^{3}$ provides all exponentiation 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