Grzegorczyk hierarchy

From Wikipedia, the free encyclopedia

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.

[edit] 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() = 0);
the successor function (e.g., s(x) = x + 1);
the projection functions, which ignore arguments (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.

[edit] Relationships to other function classes

The fourth level in the hierarchy, $\mathcal{E}^3$ , is exactly the elementary recursive functions.

[edit] 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