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 ψ

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