Aucun résumé des modifications Balise : Modification en mode source |
(→ZFC) |
||
(45 versions intermédiaires par le même utilisateur non affichées) | |||
Ligne 1 : | Ligne 1 : | ||
+ | Cette page énumère diverses fonctions googologiques classées grossièrement par taux de croissance. Elles sont regroupées ''approximativement'' en fonction des théories censées prouver leur récursivité totale, et les fonctions individuelles sont également comparées à la [[hiérarchie de croissance rapide]]. |
||
− | {{Traduction}} |
||
− | This page lists various googological functions arranged roughly by growth rate. They are grouped ''roughly'' by what theories are expected to prove them total recursive, and individual functions are also compared to the [[hiérarchie de croissance rapide]]. |
||
− | *<math>\approx</math> |
+ | *<math>\approx</math> signifie que deux fonctions ont des taux de croissance "comparables" dans un sens non fixé. |
− | *<math>></math> |
+ | *<math>></math> signifie qu'une fonction a une croissance nettement supérieure à l'autre. |
− | *<math>\geq</math> |
+ | *<math>\geq</math> signifie que l'on ne sait pas exactement si une fonction dépasse l'autre ou non. |
− | *( |
+ | *(limite) signifie que la fonction a de nombreux arguments, et que le taux de croissance est trouvé en diagonalisant sur eux. |
− | == |
+ | == Récursif primitif == |
− | + | Ces fonctions sont toutes bornées par des {{wfr|Fonction_récursive_primitive|fonctions récursif primitif}} et on pense que la plupart peuvent être prouvées totales dans le cadre de la {{w|primitive recursive arithmetic}} (PRA). |
|
− | *Successor function |
+ | *Successor function n+1 = f<sub>0</sub>(n) |
− | *Addition |
+ | *Addition a+b = f<sup>b</sup><sub>0</sub>(a) |
− | *Multiplication |
+ | *Multiplication a × b > f<sub>1</sub>(n) (limite) |
− | *Exponentiation < |
+ | *Exponentiation a<sup>b</sup> {{ap}} f<sub>2</sub>(n) (limite) |
− | *Factorial |
+ | *Factorial n! {{ap}} f<sub>2</sub>(n) |
− | *[[Tétration]] |
+ | *[[Tétration]] a{{tet}}b {{ap}} f<sub>3</sub>(n) (limite) |
− | *[[Pentation]] |
+ | *[[Pentation]] a{{pent}}b {{ap}} f<sub>4</sub>(n) (limite) |
− | *[[Fonction wow]] |
+ | *[[Fonction wow]] = f<sub>4</sub>(n) |
− | *[[Notation de Steinhaus-Moser|Notation du cercle]] |
+ | *[[Notation de Steinhaus-Moser|Notation du cercle]] Circle(n) {{ap}} f<sub>4</sub>(n) |
− | *Hexation < |
+ | *Hexation a{{up}}<sup>4</sup>b {{ap}} f<sub>5</sub>(n) (limite) |
== RCA<sub>0</sub> == |
== RCA<sub>0</sub> == |
||
− | + | La totalité de ces fonctions ne peut être prouvée dans RCA<sub>0</sub> (see {{wfr|Arithmétique_du_second_ordre|second-order arithmetic}}) et elles [[:en:Eventual domination|finissent par dominer]] toutes les fonctions récursives primitives. |
|
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
+ | *[[Notation des puissances itérées]] a{{up}}<sup>n</sup>b {{ap}} f<sub>ω</sub>(n) (limite) |
||
− | The following functions eventually dominate all multirecursive functions but are still provably recursive within Peano arithmetic (PA). |
||
⚫ | |||
+ | *[[Notation hyper-E]] E# {{ap}} f<sub>ω</sub>(n) (limite) |
||
⚫ | |||
⚫ | |||
⚫ | |||
− | en cours |
||
+ | Les fonctions suivantes finissent par dominer toutes les fonctions multirécursive mais sont toujours prouvées récursives dans l'arithmétique de Peano. |
||
+ | |||
+ | * [[Fonction d'Ackermann multivariable]] <math>\approx f_{\omega^\omega}(n)</math> (limite) |
||
⚫ | |||
⚫ | |||
+ | * [[Application s(n)]] <math>\approx f_{\omega^\omega}(n)</math> |
||
== ATR<sub>0</sub> == |
== ATR<sub>0</sub> == |
||
+ | Partant de là, la totalité de ces fonctions n'est pas prouvable en arithmétique de Peano. |
||
− | Starting from here, the totality of these functions is not provable in Peano arithmetic. |
||
+ | *[[Suite de Goodstein]] G(n) <math>\approx f_{\varepsilon_0}(n)</math> |
||
− | en cours |
||
+ | *[[Hydre de Kirby-Paris]] hydra(n) <math>\approx f_{\varepsilon_0}(n)</math> |
||
+ | *[[Vers de Beklemishev]] worm(n) <math>\approx f_{\varepsilon_0}(n)</math> |
||
+ | *[[Séquence primitif]] P(n) <math>\approx f_{\varepsilon_0}(n)</math> |
||
+ | *[[Application m(n)]] <math>\approx f_{\varepsilon_0}(n)</math> |
||
+ | *[[marxen.c]] h(g(n),n) |
||
== ZFC == |
== ZFC == |
||
+ | Ces fonctions ne peuvent pas être prouvées totales dans l'induction arithmétique transfinie mais sont censées être prouvées totales dans ZFC. |
||
− | These functions cannot be proved total in arithmetical transfinite induction but are believed to be provably total in ZFC. |
||
+ | |||
+ | * [[TREE(3)|TREE(n)]] > tree(n) <math>> f_{\psi_0(\Omega^\omega)}(n)</math> |
||
+ | * [[Séquence de la paire]] Pair(n) <math>\approx f_{\psi_0(\Omega_\omega)}(n)</math> avec la fonction de Buchholz ψ |
||
+ | * [[Séquence hyper primitif]] <math>\approx f_{\psi_0(\Omega_{\omega})}(n)</math> |
||
+ | * [[Notation de la séquence en escalier]] <math>\approx f_{\psi_0(\Omega_{\omega})}(n)</math> |
||
+ | * [[SCG(13)|SCG(n)]] <math>\geq f_{\psi_0(\Omega_\omega)}(n)</math> avec la fonction de Buchholz ψ |
||
+ | * [[Hydre de Buchholz]] BH(n) <math>\approx f_{\psi_0(\varepsilon_{\Omega_\omega + 1})}(n)</math> avec la fonction de Buchholz ψ |
||
+ | |||
+ | == Des théories d'ensemble plus solides == |
||
+ | Ces fonctions ne peuvent pas être prouvées totales dans ZFC, mais sont connues pour être prouvées totales dans des théories d'ensemble plus fortes. |
||
+ | *[[Table Laver]] q(n) defined in ZFC + I3 (rank-into-rank cardinal) |
||
− | en cours |
||
− | == |
+ | == Problème ouverte == |
− | These functions cannot be proven total in ZFC, but are known to be provably total in stronger set theories. |
||
+ | * [[Système de matrice de Bashicu]] La terminaison du calcul est un problème ouvert |
||
− | en cours |
||
+ | * [[Séquence Y]] La terminaison du calcul est un problème ouvert |
||
− | == |
+ | == Fonctions non calculables == |
+ | Ces fonctions ne sont pas calculables, et ne peuvent pas être évaluées par des programmes informatiques en temps fini. |
||
− | These functions are uncomputable, and cannot be evaluated by computer programs in finite time. |
||
− | *[[ |
+ | * Fonction du [[castor affairé]] |
[[en:List of functions]] |
[[en:List of functions]] |
Dernière version du 16 octobre 2021 à 05:53
Cette page énumère diverses fonctions googologiques classées grossièrement par taux de croissance. Elles sont regroupées approximativement en fonction des théories censées prouver leur récursivité totale, et les fonctions individuelles sont également comparées à la hiérarchie de croissance rapide.
- signifie que deux fonctions ont des taux de croissance "comparables" dans un sens non fixé.
- signifie qu'une fonction a une croissance nettement supérieure à l'autre.
- signifie que l'on ne sait pas exactement si une fonction dépasse l'autre ou non.
- (limite) signifie que la fonction a de nombreux arguments, et que le taux de croissance est trouvé en diagonalisant sur eux.
Récursif primitif
Ces fonctions sont toutes bornées par des fonctions récursif primitif et on pense que la plupart peuvent être prouvées totales dans le cadre de la primitive recursive arithmetic (PRA).
- Successor function n+1 = f0(n)
- Addition a+b = fb0(a)
- Multiplication a × b > f1(n) (limite)
- Exponentiation ab ≈ f2(n) (limite)
- Factorial n! ≈ f2(n)
- Tétration a↑↑b ≈ f3(n) (limite)
- Pentation a↑↑↑b ≈ f4(n) (limite)
- Fonction wow = f4(n)
- Notation du cercle Circle(n) ≈ f4(n)
- Hexation a↑4b ≈ f5(n) (limite)
RCA0
La totalité de ces fonctions ne peut être prouvée dans RCA0 (see second-order arithmetic) et elles finissent par dominer toutes les fonctions récursives primitives.
- Fonction d'Ackermann A(n,n) ≈ fω(n)
- Notation des puissances itérées a↑nb ≈ fω(n) (limite)
- Notation de Steinhaus-Moser fω(n) (limite)
- Notation hyper-E E# ≈ fω(n) (limite)
- Graham's function gn ≈ fω+1(n)
- Notation des flèches chaînées
Peano
Les fonctions suivantes finissent par dominer toutes les fonctions multirécursive mais sont toujours prouvées récursives dans l'arithmétique de Peano.
- Fonction d'Ackermann multivariable (limite)
- Notation des tableaux (limite)
- Notation hyper-E étendue (limite)
- Application s(n)
ATR0
Partant de là, la totalité de ces fonctions n'est pas prouvable en arithmétique de Peano.
- Suite de Goodstein G(n)
- Hydre de Kirby-Paris hydra(n)
- Vers de Beklemishev worm(n)
- Séquence primitif P(n)
- Application m(n)
- marxen.c h(g(n),n)
ZFC
Ces fonctions ne peuvent pas être prouvées totales dans l'induction arithmétique transfinie mais sont censées être prouvées totales dans ZFC.
- TREE(n) > tree(n)
- Séquence de la paire Pair(n) avec la fonction de Buchholz ψ
- Séquence hyper primitif
- Notation de la séquence en escalier
- SCG(n) avec la fonction de Buchholz ψ
- Hydre de Buchholz BH(n) avec la fonction de Buchholz ψ
Des théories d'ensemble plus solides
Ces fonctions ne peuvent pas être prouvées totales dans ZFC, mais sont connues pour être prouvées totales dans des théories d'ensemble plus fortes.
- Table Laver q(n) defined in ZFC + I3 (rank-into-rank cardinal)
Problème ouverte
- Système de matrice de Bashicu La terminaison du calcul est un problème ouvert
- Séquence Y La terminaison du calcul est un problème ouvert
Fonctions non calculables
Ces fonctions ne sont pas calculables, et ne peuvent pas être évaluées par des programmes informatiques en temps fini.
- Fonction du castor affairé