Wiki Googologie
Advertisement
Wiki Googologie

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.

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.

ATR0

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

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.

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

Fonctions non calculables

Ces fonctions ne sont pas calculables, et ne peuvent pas être évaluées par des programmes informatiques en temps fini.

Advertisement