Hiérarchie de Grzegorczyk

Tout d'abord on introduit un ensemble infini de fonctions notées ${\displaystyle E_{i}}$ pour tout entier naturel ${\displaystyle i}$.

On pose ${\displaystyle E_{0}:(x,y)\mapsto x+y}$ et ${\displaystyle E_{1}:x\mapsto x^{2}+2}$. En d'autre terme, ${\displaystyle E_{0}}$ est la fonction d'addition et ${\displaystyle E_{1}}$ est une fonction unaire qui élève au carré son argument et ajoute ${\displaystyle 2}$.

Ensuite, pour tout entier ${\displaystyle n\geqslant 2}$, on définit

${\displaystyle E_{n}:x\mapsto {\begin{cases}2&{\text{si }}x=0\\E_{n-1}(E_{n}(x-1))&{\text{sinon}}\end{cases}}}$

On peut alors définir la hiérarchie de Grzegorczyk. ${\displaystyle {\mathcal {E}}^{n}}$, la n-ième classe (ou niveau) de la hiérarchie de Grzegorczyk est le plus petit ensemble qui contient

1. ${\displaystyle E_{k}}$ pour ${\displaystyle k<n}$,
2. la fonction nulle,
3. la fonction successeur (${\displaystyle S(x)=x+1}$),
4. les projections (${\displaystyle p_{i}^{m}(t_{1},t_{2},\ldots ,t_{m})=t_{i}}$),

et stable par

1. composition de fonction (si ${\displaystyle f}$, ${\displaystyle g_{1}}$, ${\displaystyle g_{2}}$,... ,${\displaystyle g_{m}}$ sont des fonctions de ${\displaystyle {\mathcal {E}}^{n}}$, alors ${\displaystyle f({\bar {u}})=h(g_{1}({\bar {u}}),g_{2}({\bar {u}}),\dots ,g_{m}({\bar {u}}))}$ l'est aussi),
2. récursion bornée, (si ${\displaystyle g}$, ${\displaystyle h}$ et ${\displaystyle j}$ sont des fonctions de ${\displaystyle {\mathcal {E}}^{n}}$ et que ${\displaystyle f}$ est telle que ${\displaystyle \forall t,\forall {\bar {u}},f(t,{\bar {u}})\leqslant j(t,{\bar {u}})}$, ${\displaystyle f(0,{\bar {u}})=g({\bar {u}})}$ et ${\displaystyle f(t+1,{\bar {u}})=h(t,{\bar {u}},f(t,{\bar {u}}))}$, alors ${\displaystyle f}$ est aussi une fonction de ${\displaystyle {\mathcal {E}}^{n}}$).

On a

${\displaystyle {\mathcal {E}}^{0}\subseteq {\mathcal {E}}^{1}\subseteq {\mathcal {E}}^{2}\subseteq \cdots }$

puisque ${\displaystyle \{E_{k}\mid k<0\}\subseteq \{E_{k}\mid k<1\}\subseteq \{E_{k}\mid k<2\}\subseteq \cdots }$.

En fait, l'inclusion est stricte (Rose 1984; Gakwaya 1997)

${\displaystyle {\mathcal {E}}^{0}\subsetneq {\mathcal {E}}^{1}\subsetneq {\mathcal {E}}^{2}\subsetneq \cdots }$

parce que l'hyperopération ${\displaystyle H_{n}}$ appartient à ${\displaystyle {\mathcal {E}}^{n}}$ mais pas à ${\displaystyle {\mathcal {E}}^{n-1}}$.

• ${\displaystyle {\mathcal {E}}^{0}}$ contient des fonctions comme ${\displaystyle x\mapsto x}$, ${\displaystyle x\mapsto x+1}$, ${\displaystyle x\mapsto x+2}$,
• ${\displaystyle {\mathcal {E}}^{1}}$ contient toutes les fonctions d'addition telles que ${\displaystyle x\mapsto 4x}$, ${\displaystyle (x,y)\mapsto x+y}$,
• ${\displaystyle {\mathcal {E}}^{2}}$ contient les fonctions de multiplication, telles que ${\displaystyle (x,y)\mapsto xy}$, ${\displaystyle x\mapsto x^{4}}$ ,
• ${\displaystyle {\mathcal {E}}^{3}}$ contient les fonctions exponentiation, comme ${\displaystyle (x,y)\mapsto x^{y}}$, ${\displaystyle x\mapsto 2^{2^{2^{x}}}}$. Cet ensemble est égal à celui des fonctions élémentaires,
• ${\displaystyle {\mathcal {E}}^{4}}$ contient la tétration.

La définition de ${\displaystyle {\mathcal {E}}^{n}}$ est la même que celle des fonctions primitives récursives, ${\displaystyle PR}$, sauf que la construction récursive est bornée (${\displaystyle f(t,{\bar {u}})\leq j(t,{\bar {u}})}$ pour une certaine fonction ${\displaystyle j\in {\mathcal {E}}^{n}}$) et les fonctions ${\displaystyle (E_{k})_{k<n}}$ sont clairement comprises dans ${\displaystyle {\mathcal {E}}^{n}}$. Par conséquent, la hiérarchie de Grzegorczyk peut être vue comme une façon de limiter la puissance de la récursion primitive.

Il est clair que les fonctions de chaque niveau sont primitives récursives (i.e. ${\displaystyle {\mathcal {E}}^{n}\subseteq PR}$) et par conséquent

${\displaystyle \bigcup _{n}{{\mathcal {E}}^{n}}\subseteq PR}$

On peut aussi montrer que toute fonction primitive récursive est présente dans la hiérarchie de Grzegorczyk (Rose 1984; Gakwaya 1997) soit

${\displaystyle \bigcup _{n}{{\mathcal {E}}^{n}}=PR}$

et les ensembles ${\displaystyle {\mathcal {E}}^{0},{\mathcal {E}}^{1}\setminus {\mathcal {E}}^{0},{\mathcal {E}}^{2}\setminus {\mathcal {E}}^{1},\dots ,{\mathcal {E}}^{n}\setminus {\mathcal {E}}^{n-1},\ldots }$ forment une partition de l'ensemble des fonctions primitives récursives ${\displaystyle PR}$.

La hiérarchie de Grzegorczyk peut être étendue aux ordinaux transfinis. On définit alors la hiérarchie de croissance rapide. Pour cela, la définition des ${\displaystyle E_{\alpha }}$ doit être étendue pour les ordinaux limites, ils sont en effet déjà définis pour les ordinaux successeurs par ${\displaystyle E_{\alpha +1}(n)=E_{\alpha }^{n}(2)}$. S'il y a une méthode standard de définir une suite fondamentale ${\displaystyle \lambda _{m}}$ dont l'ordinal limite est ${\displaystyle \lambda }$ alors la génération de ces fonctions peut se définir comme ${\displaystyle E_{\lambda }(n)=E_{\lambda _{n}}(n)}$. Cependant, cette définition dépend de la suite fondamentale. Rose (1984) propose une méthode standard pour tout ordinal ${\displaystyle \alpha <\varepsilon _{0}}$.

L'extension originale est due à Martin Löb et Stan S. Wainer (1970) et est parfois appelée hiérarchie de Löb–Wainer.

• Brainerd, W.S., Landweber, L.H. (1974), Theory of Computation, Wiley, (ISBN 0-471-09585-0)
• 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, Rozprawy matematyczne, Vol 4, p. 1–45.
• Löb, M.H. and Wainer, S.S., "Hierarchies of Number Theoretic Functions I, II: A Correction," Arch. Math. Logik Grundlagenforschung 14, 1970 p. 198–199.
• Rose, H.E., "Subrecursion: Functions and hierarchies", Oxford University Press, New York, USA, 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)

• Portail de l'informatique théorique