FANDOM


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 fast-growing hierarchy.

  • \(\approx\) means that two functions have "comparable" growth rates in some unfixed sense.
  • \(>\) means that one function significantly overgrows the other.
  • \(\geq\) means that it is not known exactly whether one function overgrows the other or not.
  • (limit) means that the function has many arguments, and the growth rate is found by diagonalizing over them.

Be careful that for computable functions A and B, even if the weakest theory among those which are known to prove the totality of B can prove the totality of A, B does not necessarily eventually dominate A. Similarly, the uncomputability of a function does not mean that it eventually dominates all total computable functions. In other words, the order of this list does not mean the order of the growth rate.

Primitive recursive

These functions are all primitive recursive and can be proved total within the primitive recursive arithmetic (PRA).

RCA0

The totality of these functions cannot be proved in RCA0 (see second-order arithmetic) and they eventually dominate all primitive recursive functions.

PA

The following functions eventually dominate all multirecursive functions but are still provably recursive within Peano arithmetic (PA).

ATR0

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

ZFC

These functions cannot be proved total in arithmetical transfinite induction but are believed to be provably total in \(\textrm{ZFC}\). It does not mean that the totality is actually verified, and actually the list contains functions whose totality or even computability is not known in the current googology community. Also, \(\vartheta\) with inputs larger than \(\Omega_2\) and \(\psi\) with inputs larger than \(\varepsilon_{\Omega_{\omega}+1}\) in estimations are unspecified (and possibly ill-defined) OCFs, and hence those estimations are meaningless. Also, other estimations are not necessarily verified, and might be just expectations, i.e. conjectural one without proofs.

Stronger set theories

These functions cannot be proven total in \(\textrm{ZFC}\), but are known to be provably total in stronger set theories.

Uncomputable functions

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

Other

The following are functions which are not single maps:

  • Slow-growing hierarchy, Hardy hierarchy, Fast-growing hierarchy. These three hierarchies can be extended indefinitely, as long as ordinals and their fundamental hierarchies can be defined. Although they are litterally uncomputable, their segments can be interpreted into computable functions if ordinals are replaced by terms in an ordinal notation and fundamental sequences are given by an algorithm on expressions.
  • BEAF. BEAF is not formalized and well-defined beyond tetrational arrays, so there are multiple interpretations.
  • Lossy channel systems and priority channel systems. The complexity classes of some decision problems are googologically large, but no single fast-growing function or number has been extracted from these.

References

Community content is available under CC-BY-SA unless otherwise noted.