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) = 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₀ 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, Γ₀, 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 »^[1].

La hiérarchie de Wainer

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

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

si λ = ω^α₁ + ... + ω^α_k−1 + ω^α_k avec α₁ ≥ ... ≥ α_k−1 ≥ α_k, alors λ[n] = ω^α₁ + ... + ω^α_k−1 + ω^α_k[n],
si λ = ω^α+1, alors λ[n] = ω^αn,
si λ = ω^α pour un ordinal limite α, alors λ[n] = ω^α[n],

et

si λ = ε₀, 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 α < ε₀ (excluant f_ε₀ 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 α < ε₀ 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 α < ε₀. Ainsi, on ne peut pas démontrer que la fonction f_ε₀ est une application à l'aide uniquement des axiomes de Peano.
La fonction de Goodstein croît approximativement comme f_ε₀, et domine tous les f_α pour α < ε₀, 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 α < β < ε₀, 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_ω²(n).

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

f₀(n) = n + 1
f₁(n) = f₀ⁿ(n) = n + n = 2n
f₂(n) = f₁ⁿ(n) = 2ⁿn
f₃(n) = f₂ⁿ(n) ≥ 2 ↑↑ n pour n ≥ 2 (en utilisant la notation des flèches de Knuth)
f_k+1(n) = f_kⁿ(n) > (2 ↑^k-1)ⁿ 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 (ω ≤ α ≤ ε₀) :

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) > (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ⁿ(1), et en particulier
f_ω+1(64) > f_ω⁶⁴(6) > G, le nombre de Graham (G = g₆₄ dans la suite définie par g₀ = 4, g_k+1 = 3 ↑^g_k 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_ω²(n) = f_ωn(n) > (n → n → ... → n → n) (avec n flèches →)
f_ε₀(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^[3] à 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$ ).

Notes et références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Fast-growing hierarchy » (voir la liste des auteurs).

↑ Prömel, Thumser et Voigt 1991, p. 348.
↑ Gallier 1991 ; Prömel, Thumser et Voigt 1991.
↑ Caicedo 2007, Theorem 1.11.

Annexes

Bibliographie

(en) W. Buchholz et S. S. Wainer, "Provably Computable Functions and the Fast Growing Hierarchy". Logic and Combinatorics, édité par S. Simpson, Contemporary Mathematics, Vol. 65, AMS (1987), 179-198.
(en) Andrés Eduardo Caicedo, « Goodstein's function », Revista Colombiana de Matemáticas, vol. 41, n^o 2,‎ 2007, p. 381-391 (lire en ligne).
(en) E. A. Cichon et S. S. Wainer, « The slow-growing and the Grzegorczyk hierarchies », The Journal of Symbolic Logic, vol. 48, n^o 2,‎ 1983, p. 399-408 (ISSN 0022-4812, DOI 10.2307/2273557), lien Math Reviews
(en) Jean H. Gallier, « What's so special about Kruskal's theorem and the ordinal Γ₀? A survey of some results in proof theory », Ann. Pure Appl. Logic, vol. 53, n^o 3,‎ 1991, p. 199-260 (DOI 10.1016/0168-0072(91)90022-E, lire en ligne), lien Math Reviews, PDF's: part 1 2 3 (en particulier partie 3, section 12, pp. 59-64, "A Glimpse at Hierarchies of Fast and Slow Growing Functions").
Jean-Yves Girard, « Π¹₂-logic. I. Dilators », Annals of Mathematical Logic, vol. 21, n^o 2,‎ 1981, p. 75-219 (ISSN 0003-4843, DOI 10.1016/0003-4843(81)90016-4), lien Math Reviews
(en) M. H. Löb et S. S. Wainer, "Hierarchies of number theoretic functions", Arch. Math. Logik 13 (1970). Correction, Arch. Math. Logik 14 (1971). Part I DOI 10.1007/BF01967649, Part 2 DOI 10.1007/BF01973616, Corrections DOI 10.1007/BF01991855.
(en) H. J. Prömel, W. Thumser et B. Voigt, « Fast growing functions based on Ramsey theorems », Discrete Mathematics, vol. 95, n^os 1-3,‎ décembre 1991, p. 341-358 (DOI 10.1016/0012-365X(91)90346-4).
(en) S. S. Wainer, "Slow Growing Versus Fast Growing". Journal of Symbolic Logic 54(2) (1999), 608-614.

Articles connexes

Portail de l'informatique théorique

[1] Prömel, Thumser et Voigt 1991, p. 348.

[2] Gallier 1991 ; Prömel, Thumser et Voigt 1991.

[3] Caicedo 2007, Theorem 1.11.

[1]

[2]

[3]