The Grzegorczyk hierarchy (, Polish pronunciation: [ɡʐɛˈɡɔrt͡ʂɨk]), named after the Polish logician Andrzej Grzegorczyk, is a hierarchy of functions used in computability theory. 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.
Definition First we introduce an infinite set of functions, denoted Ei for some natural number i. We define
E 0 ( x , y ) = x + y E 1 ( x ) = x 2 + 2 E n + 2 ( 0 ) = 2 E n + 2 ( x + 1 ) = E n + 1 ( E n + 2 ( x ) ) {\displaystyle {\begin{array}{lcl}E_{0}(x,y)&=&x+y\\E_{1}(x)&=&x^{2}+2\\E_{n+2}(0)&=&2\\E_{n+2}(x+1)&=&E_{n+1}(E_{n+2}(x))\\\end{array}}}
E 0 {\displaystyle E_{0}} is the addition function, and E 1 {\displaystyle E_{1}} is a unary function which squares its argument and adds two. Then, for each n greater than 1, E n ( x ) = E n − 1 x ( 2 ) {\displaystyle E_{n}(x)=E_{n-1}^{x}(2)} , i.e. the x-th iterate of E n − 1 {\displaystyle E_{n-1}} evaluated at 2. From these functions we define the Grzegorczyk hierarchy. E n {\displaystyle {\mathcal {E}}^{n}} , the n-th set in the hierarchy, contains the following functions:
… excerpt ends here. Continue reading the full article.
