Liste des fonctions

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‏‎.

• $\approx$ 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.
• $\geq$ 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 = f₀(n)
• Addition a+b = f^b₀(a)
• Multiplication a × b > f₁(n) (limite)
• Exponentiation a^b ≈ f₂(n) (limite)
• Factorial n! ≈ f₂(n)
• Tétration a↑↑b ≈ f₃(n) (limite)
• Pentation a↑↑↑b ≈ f₄(n) (limite)
• Fonction wow = f₄(n)
• Notation du cercle Circle(n) ≈ f₄(n)
• Hexation a↑⁴b ≈ f₅(n) (limite)

RCA₀

La totalité de ces fonctions ne peut être prouvée dans RCA₀ (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↑ⁿb ≈ f_ω(n) (limite)
• Notation de Steinhaus-Moser‏‎ f_ω(n) (limite)
• Notation hyper-E E# ≈ f_ω(n) (limite)
• Graham's function g_n ≈ f_ω+1(n)
• Notation des flèches chaînées $cg(n) \approx f_{\omega^2}(n)$

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 $\approx f_{\omega^\omega}(n)$ (limite)

ATR₀

Starting from here, the totality of these functions is not provable in Peano arithmetic.

• Suite de Goodstein $G(n) \approx f_{\varepsilon_0}(n)$
• m(n) application $\approx f_{\varepsilon_0}(n)$
• Hydre de Kirby-Paris hydra(n) $\approx f_{\varepsilon_0}(n)$
• Vers de Beklemishev worm(n) $\approx f_{\varepsilon_0}(n)$
• marxen.c $h(g(n),n)$

ZFC

These functions cannot be proved total in arithmetical transfinite induction but are believed to be provably total in ZFC.

• Nombre de séquence de la paire Pair(n) $\approx f_{\psi_0(\Omega_{\omega})}(n)$ with respect to Buchholz's function
• SCG(n) $\geq f_{\psi_0(\Omega_\omega)}(n)$ with respect to Buchholz's function
• Hydre de Buchholz BH(n) $\approx f_{\psi_0(\varepsilon_{\Omega_\omega + 1})}(n)$ with respect to Buchholz's function

Stronger set theories

These functions cannot be proven total in ZFC, but are known to be provably total in stronger set theories.

• Fonction Laver q(n) defined in ZFC + I3 (rank-into-rank cardinal)

Uncomputable functions

These functions are uncomputable, and cannot be evaluated by computer programs in finite time.

• Castor affairé‏‎