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
These functions are all primitive recursive and can be proved total within the primitive recursive arithmetic (PRA)
- Addition \(a+b > f_0(n)\)
- Multiplication \(a \times b > f_1(n)\)
- Exponentiation \(a^b \approx f_2(n)\)
- Factorial (and most of its extensions) \(n! \approx f_2(n)\)
- Latin square
- Superfactorial (Sloane and Plouffe)
- Hyperfactorial
- Bop-counting function (not primitive recursive, but upper-bounded by PR functions)
- Double exponential functions \(\approx a^{a^b} \approx f_2(f_2(n)) \)
- Torian \(T(x) = x!x\)
- Exponential factorial \(\approx f_3(n)\)
- Tetration \({^{b}a} \approx f_3(n)\)
- Big Ass Number \(\text{ban}(n) = n^{^nn} = {}^{n + 1}n\)
- Superfactorial (Pickover)
- Pentation \(a \uparrow\uparrow\uparrow b\approx f_4(n)\)
- Really Big Ass Number \(\text{rban}(n) = n^{n \uparrow\uparrow\uparrow n}\)
- Circle notation \(\approx f_4(n)\)
- Hexation \(a \uparrow^{4} b \approx f_5(n)\)
- Heptation \(a \uparrow^{5} b \approx f_6(n)\)
- Octation \(a \uparrow^{6} b \approx f_7(n)\)
- Enneation \(a \uparrow^{7} b \approx f_8(n)\)
- Decation \(a \uparrow^{8} b \approx f_9(n)\)
- Undecation \(a \uparrow^{9} b \approx f_{10}(n)\)
- Doedecation \(a \uparrow^{10} b \approx f_{11}(n)\)
- Tredecation \(a \uparrow^{11} b \approx f_{12}(n)\)
RCA0
The totality of these functions cannot be proved in RCA0 (see second-order arithmetic) and they eventually dominate all primitive recursive functions.
- Weak goodstein function \(g(n) \approx f_\omega(n)\)
- Ackermann function \(A(n,n) \approx f_\omega(n)\)
- Ackermann numbers \(\approx f_\omega(n)\), the limit of the hyper operators in general
- Friedman's vector reduction problem
- Mythical tree problem
- Sudan function \(F_n(x,y) \approx f_\omega(n)\)
- Steinhaus-Moser notation \(\approx f_\omega(n)\)
- Davenport-Schinzel sequence
- Arrow notation (both variants) \(a \uparrow^{n} b \approx f_\omega(n)\)
- Psi Notation \(\approx f_\omega(n)\)
- |T[k]| function \(\approx f_\omega(n)\)
- Hyper-E notation \(E\# \approx f_\omega(n)\) (limit)
- Graham's function \(g_n \approx f_{\omega+1}(n)\)
- Exploding Tree Function \(E(n) \approx f_{\omega+1}(n)\)
- Expansion \(a \{\{1\}\} b \approx f_{\omega+1}(n)\)
- Multiexpansion \(a \{\{2\}\} b \approx f_{\omega+2}(n)\)
- Powerexpansion \(a \{\{3\}\} b \approx f_{\omega+3}(n)\)
- Expandotetration \(a \{\{4\}\} b \approx f_{\omega+4}(n)\)
- Explosion \(a \{\{\{1\}\}\} b \approx f_{\omega 2+1}(n)\)
- Multiexplosion \(a \{\{\{2\}\}\} b \approx f_{\omega 2+2}(n)\)
- Powerexplosion \(a \{\{\{3\}\}\} b \approx f_{\omega 2+3}(n)\)
- Explodotetration \(a \{\{\{4\}\}\} b \approx f_{\omega 2+4}(n)\)
- Copy Notation \(\approx f_{\omega3}(n)\)
- Detonation \(\{a,b,1,4\} \approx f_{\omega 3+1}(n)\)
- Pentonation \(\{a,b,1,5\} \approx f_{\omega 4+1}(n)\)
- Hexonation \(\{a,b,1,6\} \approx f_{\omega 5+1}(n)\)
- Heptonation \(\{a,b,1,7\} \approx f_{\omega 6+1}(n)\)
- Octonation \(\{a,b,1,8\} \approx f_{\omega 7+1}(n)\)
- Ennonation \(\{a,b,1,9\} \approx f_{\omega 8+1}(n)\)
- Deconation \(\{a,b,1,10\} \approx f_{\omega 9+1}(n)\)
- CG function \(cg(n) \approx f_{\omega^2}(n)\)
- Megotion \(\{a,b,1,1,2\} \approx f_{\omega^2+1}(n)\)
- BOX_M̃ function \(\widetilde{M}_n \approx f_{\omega^2+1}(n)\)
- Multimegotion \(\{a,b,2,1,2\} \approx f_{\omega^2+2}(n)\)
- Powermegotion \(\{a,b,3,1,2\} \approx f_{\omega^2+3}(n)\)
- Megotetration \(\{a,b,4,1,2\} \approx f_{\omega^2+4}(n)\)
- Megoexpansion \(\{a,b,1,2,2\} \approx f_{\omega^2+\omega+1}(n)\)
- Multimegoexpansion \(\{a,b,2,2,2\} \approx f_{\omega^2+\omega+2}(n)\)
- Powermegoexpansion \(\{a,b,3,2,2\} \approx f_{\omega^2+\omega+3}(n)\)
- Megoexpandotetration \(\{a,b,4,2,2\} \approx f_{\omega^2+\omega+4}(n)\)
- Megoexplosion \(\{a,b,1,3,2\} \approx f_{\omega^2+\omega 2+1}(n)\)
- Megodetonation \(\{a,b,1,4,2\} \approx f_{\omega^2+\omega 3+1}(n)\)
- Gigotion \(\{a,b,1,1,3\} \approx f_{(\omega^2) 2+1}(n)\)
- Gigoexpansion \(\{a,b,1,2,3\} \approx f_{(\omega^2) 2+\omega+1}(n)\)
- Gigoexplosion \(\{a,b,1,3,3\} \approx f_{(\omega^2) 2+\omega 2+1}(n)\)
- Gigodetonation \(\{a,b,1,4,3\} \approx f_{(\omega^2) 2+\omega 3+1}(n)\)
- Terotion \(\{a,b,1,1,4\} \approx f_{(\omega^2) 3+1}(n)\)
- Petotion \(\{a,b,1,1,5\} \approx f_{(\omega^2) 4+1}(n)\)
- Hatotion \(\{a,b,1,1,6\} \approx f_{(\omega^2) 5+1}(n)\)
- Hepotion \(\{a,b,1,1,7\} \approx f_{(\omega^2) 6+1}(n)\)
- Ocotion \(\{a,b,1,1,8\} \approx f_{(\omega^2) 7+1}(n)\)
- Nanotion \(\{a,b,1,1,9\} \approx f_{(\omega^2) 8+1}(n)\)
- Uzotion \(\{a,b,1,1,10\} \approx f_{(\omega^2) 9+1}(n)\)
- Uuotion \(\{a,b,1,1,11\} \approx f_{(\omega^2) 10+1}(n)\)
- Udotion \(\{a,b,1,1,12\} \approx f_{(\omega^2) 11+1}(n)\)
- Utotion \(\{a,b,1,1,13\} \approx f_{(\omega^2) 12+1}(n)\)
- Ueotion \(\{a,b,1,1,14\} \approx f_{(\omega^2) 13+1}(n)\)
- Upotion \(\{a,b,1,1,15\} \approx f_{(\omega^2) 14+1}(n)\)
- Uhotion \(\{a,b,1,1,16\} \approx f_{(\omega^2) 15+1}(n)\)
- Uaotion \(\{a,b,1,1,17\} \approx f_{(\omega^2) 16+1}(n)\)
- Uootion \(\{a,b,1,1,18\} \approx f_{(\omega^2) 17+1}(n)\)
- Unotion \(\{a,b,1,1,19\} \approx f_{(\omega^2) 18+1}(n)\)
- Dzotion \(\{a,b,1,1,20\} \approx f_{(\omega^2) 19+1}(n)\)
- Tzotion \(\{a,b,1,1,30\} \approx f_{(\omega^2) 29+1}(n)\)
- Uzzotion \(\{a,b,1,1,100\} \approx f_{(\omega^2) 99+1}(n)\)
- Powiaination \(\{a,b,1,1,1,2\} \approx f_{\omega^3+1}(n)\)
- Multiaination \(\{a,b,2,1,1,2\} \approx f_{\omega^3+2}(n)\)
- Hurford's C function \(C(n) \approx f_{\omega^3 + \omega}(n)\)
- Expandaination \(\{a,b,1,2,1,2\} \approx f_{\omega^3+\omega+1}(n)\)
- Megodaination \(\{a,b,1,1,2,2\} \approx f_{\omega^3+\omega^2+1}(n)\)
- Powiairiation \(\{a,b,1,1,1,3\} \approx f_{(\omega^3) 2+1}(n)\)
Peano arithmetic
The following functions eventually dominate all multirecursive functions but are still provably recursive within Peano arithmetic.
- Linear array notation \(\{\underbrace{a,b\ldots y,z}_{n}\} \approx f_{\omega^\omega}(n)\) (limit)
- Extended hyper-E notation \(xE\# \approx f_{\omega^\omega}(n)\) (limit)
- n(k) function \(\approx f_{\omega^\omega}(n)\)
- The Q-supersystem \(Q_{\underbrace{1,0,0,\ldots,0,0}_n}(n) \approx f_{\omega^\omega}(n)\) (limit)
- Taro's multivariable Ackermann function \(\approx f_{\omega^\omega}(n)\) (limit)
- SAN linear array notation \(s(n,n,\ldots,n,n) \approx f_{\omega^\omega}(n)\) (limit)
- s(n) map \(\approx f_{\omega^\omega}(n)\)
- Planar array notation \(\{a,b (2) 2\} \approx f_{\omega^{\omega^2}}(n)\) (limit)
- Extended array notation (dimensional) \(\{a,b (0,1) 2\} \approx f_{\omega^{\omega^\omega}}(n)\)
- BEAF superdimensional arrays \(\{a,b (\underbrace{0,0\ldots0,0,1}_{n}) 2\} \approx f_{\omega^{\omega^{\omega^\omega}}}(n)\) (limit)
ATR0
Starting from here, the totality of these functions is not provable in Peano arithmetic.
- BEAF tetrational arrays \({^ba} \& n \approx f_{\varepsilon_0}(n)\) (limit)
- Notation Array Notation \(\approx f_{\varepsilon_0}(n)\) (limit)
- Cascading-E notation \(E\text{^} \approx f_{\varepsilon_0}(n)\) (limit)
- SAN extended array notation \(s(n,n\{1\{1\ldots\{1\{1,2\}2\}\ldots2\}2\}2) \approx f_{\varepsilon_0}(n)\) (limit)
- Circle(n) function \(\approx f_{\varepsilon_0}(n)\)
- m(n) map \(\approx f_{\varepsilon_0}(n)\)
- Goodstein function \(G(n) \approx f_{\varepsilon_0}(n)\)
- Hydra(n) function \(\approx f_{\varepsilon_0}(n)\)
- Worm(n) function \(\approx f_{\varepsilon_0}(n)\)
- X-Sequence Hyper-Exponential Notation \(\approx f_{\zeta_0}(n)\)
- m(m,n) map \(\approx f_{\zeta_0}(n)\)
- Nested Cascading-E Notation \(\approx f_{\varphi(\omega,0)}(n)\)
- Three Bracket NaN \(\approx f_{\varphi(\omega,0)}(n)\)
Faster computable functions
These functions and all those that follow cannot be proved total in arithmetical transfinite induction.
- Extended Cascading-E Notation \(\approx f_{\vartheta(\Omega^{2}\omega)}(n)\)
- Hyper-Extended Cascading-E Notation \(\approx f_{\vartheta(\Omega^{3})}(n)\)
- Extended Q-supersystem \(xQ_{\underbrace{1,0,0,\ldots,0,0}_{n}}(n) \approx f_{\vartheta(\Omega^{\omega})}(n)\) (limit)
- tree(n) function \(\approx f_{\vartheta(\Omega^\omega)}(n)\)
- TREE(n) function \(\geq f_{\vartheta(\Omega^\omega\omega)}(n)\)
- Bird's H(n) function \(\approx f_{\vartheta(\varepsilon_{\Omega+1})}(n)\)
- SAN expanding array notation \(s(n,n\{1\{1\{1\ldots\{1\{1,2'\}2'\}\ldots2'\}2'\}2\}2) \approx f_{\vartheta(\varepsilon_{\Omega+1})}(n)\) (limit)
- Bird's S(n) function (original) \(\approx f_{\vartheta(\theta_1(\Omega))}(n)\)
- Bird's U(n) function \(\approx f_{\vartheta(\Omega_\omega)}(n)\)
- SAN multiple expanding array notation \(s(n,n \{1\underbrace{''\ldots'}_{n}2\} 2) \approx f_{\vartheta(\Omega_\omega)}(n)\)
- Pair(n) function \(\approx f_{\vartheta(\Omega_\omega)}(n)\)
- SCG(n) function \(\geq f_{\psi_{\Omega_1}(\Omega_\omega)}(n)\)
- BH(n) function \(\approx f_{\psi_0(\varepsilon_{\Omega_\omega + 1})}(n)\)
- Hyperfactorial array notation \(\approx f_{\psi_0(\varepsilon_{\Omega_\omega+1})}(n)\) (limit)
- Bird's array notation \(\approx f_{\vartheta(\Omega_\Omega)}(n)\) (limit)
- Bird's S(n) function (new definition) \(\approx f_{\vartheta(\Omega_\Omega)}(n)\)
- Strong array notation
- Bashicu matrix system
- Loader.c function \(D(n)\)
- Friedman's finite promise games functions \(FPLCI(a)\), \(FPCI(a)\), \(FLCI(a)\)
- Greedy clique sequence functions \(USGCS(k)\), \(USGDCS(k)\), \(USGDCS_2(k)\) (\(USGDCS_2(n)\leq f_{\textrm{PTO}(\textrm{HUGE}+)}(n)\)
Uncomputable functions
These functions are uncomputable, and cannot be evaluated by computer programs in finite time.
- Busy beaver function
- Frantic frog function
- Placid platypus function (slow-growing)
- Weary wombat function (slow-growing)
- mth order busy beaver function
- Betti number
- Doodle function
- Xi function
- Infinite time Turing machine busy beaver
- Rayo's function
- FOOT function
Other
- 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 be extended 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.
