Hiérarchie de croissance rapide
# Hiérarchie de croissance rapide

En théorie de la calculabilité et en théorie de la démonstration, une hiérarchie de croissance rapide (parfois appelée une hiérarchie de Grzegorczyk étendue) est une famille, indexée par les ordinaux, de fonctions rapidement croissantes $f_α$ : N → N (où N est l'ensemble des entiers naturels {0, 1, …}, et α est un ordinal inférieur à un certain ordinal dénombrable généralement très grand). Un exemple fondamental est la hiérarchie de Wainer, s'étendant à tous les α < ε₀. De telles hiérarchies donnent un moyen naturel de classer des fonctions calculables d'après leur vitesse de croissance et leur complexité algorithmique ; elles permettent également d'exprimer de très grands nombres, tels que ceux produits par les suites de Goodstein, lorsque même la notation des flèches chaînées de Conway n'y suffit plus.

## Définition

Soit μ un grand ordinal dénombrable tel que, pour chaque ordinal limite α inférieur à μ, soit donnée une suite fondamentale, c'est-à-dire une suite strictement croissante d'ordinaux ayant pour limite α. On définit alors une hiérarchie de fonctions $f_α$ : N → N, pour α < μ, de la manière suivante :

* $f_{0}(n)=n+1$ ;
* $f_{\alpha +1}(n)=f_{\alpha }^{n}(n)$ ;
* $f_{\alpha }(n)=f_{\alpha [n]}(n)\,\!$ si α est un ordinal limite.

Ici, $f_α^n(n)$ = $f_α(f_α(...(f_α(n))...))$ désigne la nème itérée de $f_α$ appliquée à n, et α[n] le nème élément de la suite fondamentale choisie pour l'ordinal limite α.

La partie initiale de cette hiérarchie, formée des fonctions $f_α$ d'indice fini (c'est-à-dire avec α < ω), est souvent appelée la hiérarchie de Grzegorczyk en raison de sa relation étroite avec la hiérarchie d'ensembles de fonctions définie par lui, comme on le verra plus loin.

Généralisant encore la définition précédente, une hiérarchie d'itération est obtenue en prenant pour $f_0$ n'importe quelle fonction strictement croissante g : N → N telle que g(0) > 0.

Pour des ordinaux limites inférieurs à ε₀, il y a une définition naturelle des suites fondamentales, comme on le verra plus bas dans la description détaillée de la hiérarchie de Wainer, mais pour des ordinaux plus grands, la définition devient beaucoup plus compliquée, demandant par exemple l'utilisation des suites fondamentales de la hiérarchie de Veblen. Cependant, elle reste possible même au-delà de l'ordinal de Feferman-Schütte, $Γ_0,$ au moins jusqu'à l'ordinal de Bachmann-Howard (en). À l'aide des fonctions psi de Buchholz (en), on peut encore étendre cette définition jusqu'à l'ordinal de la $\Pi _{1}^{1}$-compréhension itérée transfiniment (voir hiérarchie analytique pour plus de détails).

Il semble peu vraisemblable qu'on puisse construire une extension explicite au-delà des ordinaux récursifs ; ainsi, Prömel remarque que, dans une telle tentative, « il surviendrait même des difficultés dans la notation des ordinaux ».

## La hiérarchie de Wainer

La hiérarchie de Wainer est le cas particulier de la hiérarchie des fonctions $f_α$ (α ≤ $ε_0)$ obtenue en définissant les séquences fondamentales de la manière suivante :

Pour les ordinaux limites λ < $ε_0,$ écrits sous la forme normale de Cantor,

* si λ = $ω^{α1}$ + ... + $ω^{αk−1}$ + $ω^{αk}$ avec $α_1$ ≥ ... ≥ $α_{k−1}$ ≥ $α_k,$ alors λ[n] = $ω^{α1}$ + ... + $ω^{αk−1}$ + $ω^{αk}[n],$
* si λ = $ω^{α+1},$ alors λ[n] = $ω^αn,$
* si λ = $ω^α$ pour un ordinal limite α, alors λ[n] = $ω^{α[n]},$

et

* si λ = $ε_0,$ prendre λ[0] = 0 et λ[n + 1] = $ω^{λ[n]}.$

Certains auteurs utilisent des définitions légèrement différentes (par exemple, $ω^{α+1}[n]$ = $ω^α(n+1),$ au lieu de $ω^α(n),$ ou ne la définissent que pour α < $ε_0$ (excluant $f_{ε0}$ de la hiérarchie).

## Propriétés des hiérarchies

* Chaque $f_α$ est une application. Si les suites fondamentales sont calculables (comme dans le cas de la hiérarchie de Wainer), chaque $f_α$ est une fonction calculable.
* Dans la hiérarchie de Wainer, $f_α$ est dominée par $f_β$ si α < β (pour deux fonctions f et g : N → N, on dit que f domine g si f(n) > g(n) pour tous les n assez grands). La même propriété est en fait vraie pour la plupart des hiérarchies mentionnées ci-dessus (quand elles correspondent à des séquences fondamentales satisfaisant une condition supplémentaire assez naturelle, la propriété de Bachmann).
* Dans la hiérarchie de Grzegorczyk, chaque fonction récursive primitive est dominée par un certain $f_α$ avec α < ω. Par conséquent, dans la hiérarchie de Wainer, toutes les fonctions récursives primitives sont dominées par $f_ω$ (laquelle est une variante de la fonction d'Ackermann).
* Pour n ≥ 3, l'ensemble ${\mathcal {E}}^{n}$ dans la hiérarchie (ensembliste) de Grzegorczyk est composé des applications calculables à plusieurs variables qui, pour des valeurs assez grandes de leurs arguments, sont calculables en temps borné par une itérée $f_{n-1}^k$ (avec k fixé) évaluée en le plus grand argument.
* Dans la hiérarchie de Wainer, chaque $f_α$ avec α < $ε_0$ est calculable par une machine de Turing dont on peut démontrer l'arrêt (pour toute valeur d'entrée) dans l'arithmétique de Peano.
* Réciproquement, toute fonction calculable par une machine de Turing dont on peut démontrer l'arrêt dans l'arithmétique de Peano est dominée par un $f_α$ de la hiérarchie de Wainer, avec α < $ε_0.$ Ainsi, on ne peut pas démontrer que la fonction $f_{ε0}$ est une application à l'aide uniquement des axiomes de Peano.
* La fonction de Goodstein croît approximativement comme $f_{ε0},$ et domine tous les $f_α$ pour α < $ε_0,$ c'est pourquoi le théorème de Goodstein ne peut être démontré dans l'arithmétique de Peano.
* Dans la hiérarchie de Wainer, si α < β < $ε_0,$ alors $f_β$ domine toute fonction calculable en temps et en espace borné par une fonction itérée $f_α^k.$

## Les fonctions des hiérarchies de croissance rapide

En dehors de la valeur $f_α(1)$ = 2 pour tout α, et des tout premiers niveaux de la hiérarchie, il est en général impossible de donner une valeur exacte de ces fonctions à l'aide des notations exponentielles usuelles, ni même à l'aide des diverses notations inventées pour décrire de très grands entiers, tant elles croissent vite. Les minorations données ci-dessous ne fournissent donc qu'un très grossier ordre de grandeur, d'ailleurs lui-même ridiculement faible dès la fonction $f_{ω2}(n).$

Les fonctions des niveaux finis de toute hiérarchie de croissance rapide coïncident avec celles de la hiérarchie de Grzegorczyk :

* $f_0(n)$ = n + 1
* $f_1(n)$ = $f_0^n(n)$ = n + n = 2n
* $f_2(n)$ = $f_1^n(n)$ = $2^nn$
* $f_3(n)$ = $f_2^n(n)$ ≥ 2 ↑↑ n pour n ≥ 2 (en utilisant la notation des flèches de Knuth)
* $f_{k+1}(n)$ = $f_k^n(n)$ > (2 $↑^{k-1})^n$ n ≥ 2 $↑^k$ n pour n ≥ 2, k < ω (où $↑^k=↑↑↑...↑↑,$ avec k flèches).

On trouve ensuite les fonctions $f_α$ de la hiérarchie de Wainer (ω ≤ α ≤ $ε_0)$ :

* $f_ω(n)$ = $f_n(n)$ > 2 $↑^{n-1}$ n > 2 $↑^{n−2}$ (n + 3) − 3 = A(n, n) pour n ≥ 2, où A est la fonction d'Ackermann (dont $f_ω$ est une version unaire).
* $f_{ω+1}(n)$ = $f_ω^n(n)$ > (2 → n → n-1 → 2) (en utilisant la notation des flèches chaînées de Conway), car si $g_k(n)$ = X → n → k, alors X → n → k+1 $=g_k^n(1),$ et en particulier
* $f_{ω+1}(64)$ > $f_ω^{64}(6)$ > G, le nombre de Graham (G = $g_{64}$ dans la suite définie par $g_0$ = 4, $g_{k+1}$ = 3 $↑^{gk}$ 3). Cela résulte de ce que $f_ω(n)$ > 2 $↑^{n-1}$ n > 3 $↑^{n-2}$ 3 + 2, et par conséquent $f_ω(g_k$ + 2) > $g_{k+1}$ + 2.
* $f_{ω+k}(n)$ > (2 → n → n-1 → k+1) > (n → n → k)
* $f_{ω2}(n)$ = $f_{ω+n}(n)$ > (n → n → n)
* $f_{ω2+k}(n)$ > (n → n → n → k)
* $f_{ω3}(n)$ > (n → n → n → n)
* $f_{ωk}(n)$ > (n → n → ... → n → n) (chaîne formée de k flèches → )
* $f_{ω2}(n)$ = $f_{ωn}(n)$ > (n → n → ... → n → n) (avec n flèches →)
* $f_{ε0}(n)$ est la première fonction de la hiérarchie de Wainer qui domine la fonction de Goodstein G(n) (laquelle peut d'ailleurs s'exprimer exactement à l'aide des fonctions $f_α$ ; ainsi, on a $G(4)=f_ω(3)$ - 2, $G(8)=f_{ω+1}(3)$ - 2, et G(19)=$\scriptstyle f_{\omega ^{\omega }}(f_{1}(f_{0}(3)))-2=f_{\omega ^{\omega }}(8)-2=f_{\omega ^{8}}(8)-2=f_{\omega ^{7}.8}(8)-2=f_{\omega ^{7}.7+8}(8)-2=\dots$).
