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 (Wagner and Wechsung 1986:43). 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 numberi. We define and . 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 2, we define , i.e. the x-th iterate of evaluated at 2.
From these functions we define the Grzegorczyk hierarchy. , the n-th set in the hierarchy, contains the following functions:
Notably, both the function and the characteristic function of the predicate from the Kleene normal form theorem are definable in a way such that they lie at level of the Grzegorczyk hierarchy. This implies in particular that every recursively enumerable set is enumerable by some -function.
Relation to primitive recursive functionsEdit
The definition of is the same as that of the primitive recursive functions, PR, except that recursion is limited ( for some j in ) and the functions are explicitly included in . 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 (Rose 1984; Gakwaya 1997), thus
and the sets partition the set of primitive recursive functions, PR.
The Grzegorczyk hierarchy can be extended to transfiniteordinals. Such extensions define a fast-growing hierarchy. To do this, the generating functions 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.
^ abHere represents a tuple of inputs to f. The notation means that f takes some arbitrary number of arguments and if , then . In the notation , the first argument, t, is specified explicitly and the rest as the arbitrary tuple . Thus, if , then . This notation allows composition and limited recursion to be defined for functions, f, of any number of arguments.
Brainerd, W.S., Landweber, L.H. (1974), Theory of Computation, Wiley, ISBN 0-471-09585-0
Cichon, E. A.; Wainer, S. S. (1983), "The slow-growing and the Grzegorczyk hierarchies", Journal of Symbolic Logic, 48 (2): 399–408, doi:10.2307/2273557, ISSN 0022-4812, MR 0704094
Gakwaya, J.–S. (1997), A survey on the Grzegorczyk Hierarchy and its Extension through the BSS Model of Computability
Grzegorczyk, A (1953). "Some classes of recursive functions" (PDF). Rozprawy matematyczne. 4: 1–45.
Löb, M.H.; Wainer, S.S. (1970). "Hierarchies of Number Theoretic Functions I, II: A Correction". Archiv für mathematische Logik und Grundlagenforschung. 14: 198–199. doi:10.1007/bf01991855.
Rose, H.E., Subrecursion: Functions and hierarchies, Oxford University Press, 1984. ISBN 0-19-853189-3
Wagner, K. and Wechsung, G. (1986), Computational Complexity, Mathematics and its Applications v. 21. ISBN 978-90-277-2146-4