原始递归函数的分层

也叫格热高契克分层(Grzegorczyk hierarchy)，是由格热高契克所提出的一种对原始递归函数分层的方法。

格热高契克定义了一簇原始递归函数f(x，y)，称为格热高契克函数：

格热高契克还定义了两种简单的函数运算：简单代入和有界原始递归。简单代入就是由n元函数f(x，…，x)得到f(ξ，…，ξ)，其中ξ(i=1，…，n)是常数或x，…，x中的某一个。

有界原始递归是由g(x，…，x)，h(x，…，x，y，z)，b(x，…，x，y)得到的满足下式的f(x，…，x，y)：

对每个n≥0，以S(x)=x+1，(x，y)=x，U(x，y)=y以及前n+1个格热高契克函数为初始函数，经有穷次使用简单代入和有界原始递归运算而得到的函数类，记作。

格热高契克证明：

(1)对每个n≥0，，

(2)是全体原始递归函数。也就是说构成原始递归函数的一个分层。

事实上就已经包括了相当多的函数，我们有：每个递归可枚举集都是某个中的函数的值域。