Fandom

Googology Wiki

List of functions

Redirected from List of googological functions

10,621pages on
this wiki
Add New Page
Talk20 Share

This page lists various googological functions arranged roughly by growth rate. They are grouped roughly by what arithmetic 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.
  • \(>\) 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.

Primitive recursive Edit

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

etc

RCA0 Edit

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

Peano arithmetic Edit

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

ATR0 Edit

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

Faster computable functions Edit

These functions and all those that follow cannot be proved total in arithmetical transfinite induction.

Uncomputable functions Edit

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

Other Edit

  • Fusible margin function. The growth rate of the \(m_1(x)\) function is an unsolved problem.
  • Laver tables. It is not yet known if corresponding function is total, and only some lower bounds are known for it.
  • Friedman's finite trees. Although suspected to be very strong, no explicit claims on the resulting functions' rate of growth have been made.
  • Slow-growing hierarchy, Hardy hierarchy, Fast-growing hierarchy. These three hierarchies can extend indefinitely, as long as ordinals and their fundamental hierarchies can be defined.
  • BEAF. BEAF is not well-defined beyond tetrational arrays, so there are mutiple 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.

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.