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 Grzegorczykhiérarchie de Grzegorczyk étendue) est une famille, indexée par les ordinaux, de fonctions rapidement croissantes f_α: N → N (où N est l'ensemble desentiers 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 α < ε₀ (en). De telles hiérarchies donnent un moyen naturel de classer des fonctions calculables d'après leur vitesse de croissance et leur complexité algorithmique ; elle 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 unehié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 fonctionshiérarchie de Grzegorczyk 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 croissante g: N → N.

Pour des ordinaux limites inférieurs à ε₀ (en), 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 Veblenfonction de Veblen. Cependant, elle reste possible même au-delà de l'ordinal de Feferman–Schütte, Γ₀ (en), 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 analytiquehiérarchie analytique pour plus de détails).

Une extension explicite au delà des ordinaux récursifsordinal récursif semble peu vraisemblable ; 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_α (α ≤ ε₀) obtenue en définissant les séquences fondamentales de la manière suivante :

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

• si λ = ω^α₁ + ... + ω^α_k−1 + ω^α_k for α₁ ≥ ... ≥ α_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_ε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), chaquef_α 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 sif(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 correspondant à 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 Grzegorczykhiérarchie 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 (aveck 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_ε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 α < ε₀, 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

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 lafonction 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 sig_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équentf_ω(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) = (n → n → n→ 1)
• 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_ε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 aG(4)=f_ω(3) - 2, G(8)=f_ω+1(3) - 2, et G(19)=$\scriptstyle f_{\omega ^{\omega }}(f_{1}(f_{0}(3)))-2$).

Voir aussi

• Grand nombre

• Théorème de Goodstein

Références

• W. Buchholz ; S.S Wainer (1987). "Provably Computable Functions and the Fast Growing Hierarchy". Logic and Combinatorics, édité par S. Simpson, Contemporary Mathematics, Vol. 65, AMS, 179-198.

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

• 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) PDF's: part 12 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)

• M.H. Löb ; S.S Wainer (1970), "Hierarchies of number theoretic functions", Arch. Math. Logik, 13. Correction, Arch. Math. Logik, 14, 1971. Part I DOI 10.1007/BF01967649, Part 2DOI 10.1007/BF01973616, Corrections DOI 10.1007/BF01991855.

• Prömel, H. J.; Thumser, W.; Voigt, B. "Fast growing functions based on Ramsey theorems", Discrete Mathematics, v.95 n.1-3, p. 341-358, Dec. 1991 DOI 10.1016/0012-365X(91)90346-4.

• Wainer, S.S (1989), "Slow Growing Versus Fast Growing". Journal of Symbolic Logic 54(2): 608-614.