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 (en) é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 α < 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^[1] 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 :

• 
• 
• 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 (en) 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 à 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 -compréhension itérée transfiniment (voir hiérarchie analytique (en) pour plus de détails).

Une extension explicite au delà des ordinaux récursifs (en) semble peu vraisemblable ; ainsi, Prӧmel remarque que, dans une telle tentative, "il surviendrait même des difficultés dans la notation des ordinaux"^[2].

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^[3] :

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_ε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 dans la hiérarchie (ensembliste) de Grzegorczyk (en) 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_ε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

En dehors de la valeur f_α(1) = 2 pour tout α, et des tous 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_ε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^[4] à l'aide des fonctions f_α ; ainsi, on a G(4)=f_ω(3) - 2, G(8)=f_ω+1(3) - 2, et G(19)=).

Notes

Voir aussi

• Grand nombre

• Théorème de Goodstein

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)

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

• E. A. Cichon, « The slow-growing and the Grzegorczyk hierarchies », dans The Journal of Symbolic Logic, vol. 48, n^o 2, 1983, p. 399–408 (ISSN 0022-4812) [lien DOI] , MR704094

• Jean H. Gallier, « What's so special about Kruskal's theorem and the ordinal Γ₀? A survey of some results in proof theory », dans Ann. Pure Appl. Logic, vol. 53, n^o 3, 1991, p. 199–260 [texte intégral, lien DOI] , MR1129778, 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 », dans Annals of Mathematical Logic, vol. 21, n^o 2, 1981, p. 75–219 (ISSN 0003-4843) [lien DOI] , MR656793

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

• H. J. Prömel, W. Thumser et B. Voigt, "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.

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

• Portail des mathématiques
• Portail de l’informatique