Hiérarchie de Grzegorczyk

La hiérarchie de Grzegorczyk – du nom du logicien polonais Andrzej Grzegorczyk – est une hiérarchie de fonctions utilisée en théorie de la calculabilité. Toutes les fonctions de la hiérarchie de Grzegorczyk sont primitives récursives et toute fonction primitive récursive apparait dans cette hiérarchie. Cette hiérarchie classe les fonctions selon leur croissance. Intuitivement, les fonctions d'un niveau croissent moins vite que les fonctions des niveaux supérieurs.

Définition

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

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

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

$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. ${\mathcal {E}}^{n}$, la n-ième classe (ou niveau) de la hiérarchie de Grzegorczyk est le plus petit ensemble qui contient

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

et stable par

1. composition de fonction (si $f$, $g_{1}$, $g_{2}$,... ,$g_{m}$ sont des fonctions de ${\mathcal {E}}^{n}$, alors $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 $g$, $h$ et $j$ sont des fonctions de ${\mathcal {E}}^{n}$ et que $f$ est telle que $\forall t,\forall {\bar {u}},f(t,{\bar {u}})\leqslant j(t,{\bar {u}})$, $f(0,{\bar {u}})=g({\bar {u}})$ et $f(t+1,{\bar {u}})=h(t,{\bar {u}},f(t,{\bar {u}}))$, alors $f$ est aussi une fonction de ${\mathcal {E}}^{n}$).

Propriétés

On a

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

puisque $\{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)

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

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

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

Relation avec les fonctions primitives récursives

La définition de ${\mathcal {E}}^{n}$ est la même que celle des fonctions primitives récursives, $PR$, sauf que la construction récursive est bornée ($f(t,{\bar {u}})\leq j(t,{\bar {u}})$ pour une certaine fonction $j\in {\mathcal {E}}^{n}$) et les fonctions $(E_{k})_{k<n}$ sont clairement comprises dans ${\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. ${\mathcal {E}}^{n}\subseteq PR$) et par conséquent

$\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

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

et les ensembles ${\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 $PR$.

Extensions

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 $E_{\alpha }$ doit être étendue pour les ordinaux limites, ils sont en effet déjà définis pour les ordinaux successeurs par $E_{\alpha +1}(n)=E_{\alpha }^{n}(2)$. S'il y a une méthode standard de définir une suite fondamentale $\lambda _{m}$ dont l'ordinal limite est $\lambda$ alors la génération de ces fonctions peut se définir comme $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 $\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.

Bibliographie

• 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)