The Grzegorczyk hierarchy (/ɡrɛˈɡɔːrtʃək/, Polish pronunciation: [ɡʐɛˈɡɔrt͡ʂɨk]), named after the Polish logician Andrzej Grzegorczyk, is a hierarchy of functions used in computability theory.
[1] Every function in the Grzegorczyk hierarchy is a primitive recursive function, and every primitive recursive function appears in the hierarchy at some level.
The hierarchy deals with the rate at which the values of the functions grow; intuitively, functions in lower levels of the hierarchy grow slower than functions in the higher levels.
First we introduce an infinite set of functions, denoted Ei for some natural number i.
is a unary function which squares its argument and adds two.
From these functions we define the Grzegorczyk hierarchy.
, the n-th set in the hierarchy, contains the following functions: In other words,
with respect to function composition and limited recursion (as defined above).
These sets clearly form the hierarchy because they are closures over the
and the characteristic function of the predicate
from the Kleene normal form theorem are definable in a way such that they lie at level
This implies in particular that every recursively enumerable set is enumerable by some
is the same as that of the primitive recursive functions, PR, except that recursion is limited (
Thus the Grzegorczyk hierarchy can be seen as a way to limit the power of primitive recursion to different levels.
It is clear from this fact that all functions in any level of the Grzegorczyk hierarchy are primitive recursive functions (i.e.
) and thus: It can also be shown that all primitive recursive functions are in some level of the hierarchy,[2][3] thus and the sets
partition the set of primitive recursive functions, PR.
Meyer and Ritchie introduced another hierarchy subdividing the primitive recursive functions, based on the nesting depth of loops needed to write a LOOP program that computes the function.
For a natural number
denote the set of functions computable by a LOOP program with LOOP and END commands nested no deeper than
[4] Fachini and Maggiolo-Schettini showed that
[5]p.63 The Grzegorczyk hierarchy can be extended to transfinite ordinals.
Such extensions define a fast-growing hierarchy.
must be recursively defined for limit ordinals (note they have already been recursively defined for successor ordinals by the relation
If there is a standard way of defining a fundamental sequence
, whose limit ordinal is
, then the generating functions can be defined
However, this definition depends upon a standard way of defining the fundamental sequence.
Rose (1984) suggests a standard way for all ordinals α < ε0.
The original extension was due to Martin Löb and Stan S. Wainer and is sometimes called the Löb–Wainer hierarchy.