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)
Notation des tableaux $\approx f_{\omega^\omega}(n)$ (limite)
Notation hyper-E étendue $xE\# \approx f_{\omega^\omega}(n)$ (limite)
Application s(n) $\approx f_{\omega^\omega}(n)$

ATR₀[]

Partant de là, la totalité de ces fonctions n'est pas prouvable en arithmétique de Peano.

Suite de Goodstein G(n) $\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)$
Séquence primitif P(n) $\approx f_{\varepsilon_0}(n)$
Application m(n) $\approx f_{\varepsilon_0}(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) $> f_{\psi_0(\Omega^\omega)}(n)$
Séquence de la paire Pair(n) $\approx f_{\psi_0(\Omega_{\omega})}(n)$ avec la fonction de Buchholz ψ
Séquence hyper primitif $\approx f_{\psi_0(\Omega_{\omega})}(n)$
Notation de la séquence en escalier $\approx f_{\psi_0(\Omega_{\omega})}(n)$
SCG(n) $\geq f_{\psi_0(\Omega_\omega)}(n)$ avec la fonction de Buchholz ψ
Hydre de Buchholz BH(n) $\approx f_{\psi_0(\varepsilon_{\Omega_\omega + 1})}(n)$ avec la fonction de Buchholz ψ