グジェゴルチク階層（ぐじぇごるちくかいそう、英: Grzegorczyk hierarchy、発音：[??????rt???k]）は計算可能性理論に基づく関数の階層である。（Wagner and Wechsung 1986:43）。名称はポーランドの論理学者アンジェイ・グジェゴルチク（英語版）に因む。グジェゴルチク階層に属す任意の関数は原始帰納的関数であり、逆に任意の原始帰納的関数はこの階層のあるレベルに現れる。この階層は関数値の増大の度合いを扱う。直観的にいえば、低い階層の関数はより高い階層の関数よりも緩やかに増加する。
定義

まず自然数 i で添字付けられた関数族 Ei を導入する。まず次のように定義する： E 0 ( x , y ) = x + y {\displaystyle E_{0}(x,y)=x+y} E 1 ( x ) = x 2 + 2 {\displaystyle E_{1}(x)=x^{2}+2} E n ( x ) = E n − 1 x ( 2 ) {\displaystyle E_{n}(x)=E_{n-1}^{x}(2)} （ただし n > 1）

これらの関数からグジェゴルチク階層を定義する。 E n {\displaystyle {\mathcal {E}}^{n}} は n番目の階層であり、次の関数からなる：
Ek （ただし k < n）

ゼロ関数 (Z(x) = 0);

後者関数 (S(x) = x + 1);

射影関数 ( p i m ( t 1 , t 2 , … , t m ) = t i {\displaystyle p_{i}^{m}(t_{1},t_{2},\dots ,t_{m})=t_{i}} );

（一般）合成関数 （もし h, g1, g2, ... と gm が E n {\displaystyle {\mathcal {E}}^{n}} に属すならば f ( u ¯ ) = h ( g 1 ( u ¯ ) , g 2 ( u ¯ ) , … , g m ( u ¯ ) ) {\displaystyle f({\bar {u}})=h(g_{1}({\bar {u}}),g_{2}({\bar {u}}),\dots ,g_{m}({\bar {u}}))} も同様）[note 1]; および

限定（原始）再帰 （もし g, h と j が E n {\displaystyle {\mathcal {E}}^{n}} に属し f ( t , u ¯ ) ≤ j ( t , u ¯ ) {\displaystyle f(t,{\bar {u}})\leq j(t,{\bar {u}})} , f ( 0 , u ¯ ) = g ( u ¯ ) {\displaystyle f(0,{\bar {u}})=g({\bar {u}})} , f ( t + 1 , u ¯ ) = h ( t , u ¯ , f ( t , u ¯ ) ) {\displaystyle f(t+1,{\bar {u}})=h(t,{\bar {u}},f(t,{\bar {u}}))} ならば、 f もまた E n {\displaystyle {\mathcal {E}}^{n}} に属す)[note 1]

換言すれば E n {\displaystyle {\mathcal {E}}^{n}} は B n = { Z , S , ( p i m ) i ≤ m , E k : k < n } {\displaystyle B_{n}=\{Z,S,(p_{i}^{m})_{i\leq m},E_{k}:k<n\}} を含み関数合成と限定原始再帰で閉じた最小の集合（閉包）である。
性質

これらの集合は明らかに階層を成す。 E 0 ⊆ E 1 ⊆ E 2 ⊆ ⋯ {\displaystyle {\mathcal {E}}^{0}\subseteq {\mathcal {E}}^{1}\subseteq {\mathcal {E}}^{2}\subseteq \cdots }

実際これらは B n {\displaystyle B_{n}} の閉包であって B 0 ⊆ B 1 ⊆ B 2 ⊆ ⋯ {\displaystyle B_{0}\subseteq B_{1}\subseteq B_{2}\subseteq \cdots } となっているからである。

これらは強い意味での包含関係が成り立つ（Rose 1984; Gakwaya 1997）。換言すれば E 0 ⊊ E 1 ⊊ E 2 ⊊ ⋯ {\displaystyle {\mathcal {E}}^{0}\subsetneq {\mathcal {E}}^{1}\subsetneq {\mathcal {E}}^{2}\subsetneq \cdots }

というのも、ハイパー演算子 H n {\displaystyle H_{n}} は E n {\displaystyle {\mathcal {E}}^{n}} に属すが E n − 1 {\displaystyle {\mathcal {E}}^{n-1}} には属さないからである。

E 0 {\displaystyle {\mathcal {E}}^{0}} は次を含む： x+1, x+2, ...

E 1 {\displaystyle {\mathcal {E}}^{1}} は全ての加法関数を備える： x+y, 4x, ...

E 2 {\displaystyle {\mathcal {E}}^{2}} は全ての乗法関数を備える： xy, x4, ...

E 3 {\displaystyle {\mathcal {E}}^{3}} は全ての指数関数を備える： xy, 222x さらにこの階層は初等帰納的関数のクラスや反復指数時間で計算可能な関数のクラスなどと一致する

E 4 {\displaystyle {\mathcal {E}}^{4}} は全てのテトレーション関数を備える。

原始帰納的関数との関係

E n {\displaystyle {\mathcal {E}}^{n}} の定義は再帰が限定 （ある j ∈ E n {\displaystyle \in {\mathcal {E}}^{n}} に対して f ( t , u ¯ ) ≤ j ( t , u ¯ ) {\displaystyle f(t,{\bar {u}})\leq j(t,{\bar {u}})} ）されていることと、 ( E k ) k < n {\displaystyle (E_{k})_{k<n}} が明示的に導入されることを除けば 原始帰納的関数のクラス PR の定義に似ている。グジェゴルチク階層は原始再帰の強さを制限しているものと見ることができる。

この事実からグジェゴルチク階層に属す全ての関数は原始帰納的関数であること（すなわち E n ⊆ P R {\displaystyle {\mathcal {E}}^{n}\subseteq PR} ）が示される。したがって ⋃ n E n ⊆ P R {\displaystyle \bigcup _{n}{{\mathcal {E}}^{n}}\subseteq PR}

さらに全ての原始帰納的関数が何れかの階層に属すことも示される（Rose 1984; Gakwaya 1997）。つまり ⋃ n E n = P R {\displaystyle \bigcup _{n}{{\mathcal {E}}^{n}}=PR}

また E 0 , E 1 − E 0 , E 2 − E 1 , … , E n − E n − 1 , … {\displaystyle {\mathcal {E}}^{0},{\mathcal {E}}^{1}-{\mathcal {E}}^{0},{\mathcal {E}}^{2}-{\mathcal {E}}^{1},\dots ,{\mathcal {E}}^{n}-{\mathcal {E}}^{n-1},\dots } は原始帰納的関数のクラス PR の分割となっている。さらに各々の領域は潰れていない。
拡張詳細は「急成長階層」を参照

グジェゴルチク階層は超限順序数に一般化できる。そのような拡張として急成長階層が定義される。