List of functions

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. (It's possible to make an uncomputable function that only outputs 0 or 1.) In other words, the order of this list does not mean the order of the growth rate.
Not all functions are shown here, but the complete list of all functions can be found in a category.
== Primitive recursive ==
These functions are all bounded by functions and it is believed that most can be proved total within the theory of (PRA).
*Successor function \(n+1 = f_0(n)\)
*Addition \(a+b = f^b_0(a)\)
*Multiplication \(a \times b > f_1(n)\) (limit)
*Exponentiation \(a^b \approx f_2(n)\) (limit, note that \(f_2(n) = 2^n \times n\))
*Factorial (and most of its extensions) \(n! \approx f_2(n)\)
*Superfactorial (Sloane and Plouffe) \(n$ \approx f_2(n)\)
*Torian \(T(x) = x!x \approx f_2(x)\)
*Hyperfactorial \(H(n) \approx f_2(n)\)
*Latin square \(L(n) \approx f_2(n)\)
*Double exponential functions \(a^{b^c} \approx f_2(f_2(n))\) (limit)
*Factorexation \(n \backslash \approx f_2(f_2(n))\)
*Googolple- \(\text{googol-}n\text{-ple-}n \approx f_2(f_2(n))\)
*Bop-counting function (not primitive recursive, but upper-bounded by primitive recursive functions, \(\theta(12)=n\) can't be proven given a natural number \(n\) in some theories including ZFC+I1)
*Exponential factorial \(a_n \approx f_3(n)\)
*Scientific notation \(x \cdot 10^{y \cdot 10^{\cdots}} \approx f_3(n)\) (limit)
*PlantStar's Debut Notation \(\approx f_3(n)\) (limit, also ill-defined)
*Tetration \({^{b}a} \approx f_3(n)\) (limit)
*Big Ass Number \(\text{ban}(n) = n^{^nn} = {}^{n + 1}n \approx f_3(n)\)
*Expostfacto function \(\mathrm{expostfacto}(n) \approx f_3(n)\)
*Superfactorial (Pickover) \(n$ \approx f_3(f_2(n))\)
*Tetrofactorial \(n!2 \approx f_4(n)\)
*Pentation \(a \uparrow\uparrow\uparrow b\approx f_4(n)\) (limit)
*Really Big Ass Number \(\text{rban}(n) = n^{n \uparrow\uparrow\uparrow n} \approx f_4(n)\)
*Wow function \(= f_4(n)\)
*Circle notation \(Circle(n) \approx f_4(n)\)
*Pentatorial \(n[5]! \approx f_5(n)\)
*Hexation \(a \uparrow^{4} b \approx f_5(n)\) (limit)
*Heptation \(a \uparrow^{5} b \approx f_6(n)\) (limit)
*Octation \(a \uparrow^{6} b \approx f_7(n)\) (limit)
*Enneation \(a \uparrow^{7} b \approx f_8(n)\) (limit)
*Decation \(a \uparrow^{8} b \approx f_9(n)\) (limit)
*Undecation \(a \uparrow^{9} b \approx f_{10}(n)\) (limit)
*Doedecation \(a \uparrow^{10} b \approx f_{11}(n)\) (limit)
*Tredecation \(a \uparrow^{11} b \approx f_{12}(n)\) (limit)
== RCA0 ==
The totality of these functions cannot be proved in RCA0 (see second-order arithmetic) and they eventually dominate all primitive recursive functions. The fast-growing hierarchy here is given by Wainer hierarchy.
*Weak Goodstein function \(g(n) \approx f_\omega(n)\)
*|T[k]| function (finite ordered tree problem) \(|T[n]| \approx f_\omega(n)\)
*Ackermann function \(A(n,n) \approx f_\omega(n)\)
*Booga- \(booga(n) \approx f_\omega(n)\)
*Mythical tree problem \(\approx f_\omega(n)\) (limit)
*Friedman's vector reduction problem \(\approx f_\omega(n)\) (limit)
*Davenport-Schinzel sequence \(\approx f_\omega(n)\) (limit)
*Arrow notation (both variants) \(a \uparrow^{n} b \approx f_\omega(n)\) (limit)
*Ackermann numbers \(\approx f_\omega(n)\), the limit of the hyper operators in general
*Sudan function \(F_n(x,y) \approx f_\omega(n)\) (limit)
*Steinhaus-Moser notation \(\approx f_\omega(n)\) (limit)
*H* function \(H^*(\underbrace{n,n,\cdots n,n}_n) \approx f_\omega(n)\) (limit)
*Hyper-E notation \(E\# \approx f_\omega(n)\) (limit)
* Psi Notation \(\approx f_\omega(n)\) (limit)
*Graham's function \(g_n \approx f_{\omega+1}(n)\)
*Mag \(\text{mag}(n)\approx f_{\omega+1}(n)\)
*Trooga- \(\text{trooga}(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)\)
*Hyperlicious function \(h_n(\underbrace{n,n,\cdots n,n}_n) \approx f_{\omega+1}(n)\) (limit)
*Multiexpansion \(a \{\{2\}\} b \approx f_{\omega+2}(n)\)
*Mixed factorial \(n^*_{(n,n)} \approx f_{\omega+2}(n)\)
*Powerexpansion \(a \{\{3\}\} b \approx f_{\omega+3}(n)\)
*Expandotetration \(a \{\{4\}\} b \approx f_{\omega+4}(n)\)
*-ag \(n\text{-ag}(n)\approx f_{\omega 2}(n)\)
*Graham Array Notation \(\approx f_{\omega 2}(n)\) (limit)
*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)\) (limit)
*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)\)
*Extended H* Function \(H^*_n(\underbrace{n,n,\cdots n,n}_n) \approx f_{\omega^2}(n)\) (limit)
*Graham Array Notation (Extended) \(\approx f_{\omega^2}(n)\) (limit)
*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)\)
*Chained arrow notation (Peter Hurford's extension) \(\approx f_{\omega^3}(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)\)
*Chained array notation \(n[\underbrace{n,n,\cdots n}_n]n \approx f_{\omega^5}(n)\) (limit)
== PA ==
The following functions eventually dominate all multirecursive functions but are still provably recursive within Peano arithmetic (PA). The fast-growing hierarchy here is given by Wainer hierarchy.
*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)
*s(n) map \(\approx f_{\omega^\omega}(n)\)
*Hyper-Moser notation \(M(n,\underbrace{0,0,\cdots0,}_nn) \approx f_{\omega^\omega}(n)\) (limit)
*Aarex's Graham Generator \(\text{Forcal}_{\underbrace{1,1,\cdots1,}_n2}(1) \approx f_{\omega^\omega}(n)\) (limit)
*Nested factorial notation \(n![\underbrace{n,n,\cdots n,n}_n] \approx f_{\omega^\omega}(n)\) (limit)
*Hyper Binary Sequences \(\left\langle 01111111\ldots\right\rangle[n] \approx f_{\omega^\omega}(n)\) (limit)
*Matthew's Function \(n\uparrow\rightarrow\uparrow n \approx f_{\omega^{\omega^2}}(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)\) (limit)
*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 following functions eventually dominate all hyperrecursive functions and the totality of these functions is not provable in PA. The fast-growing hierarchy here is given by Veblen hierarchy.
*Goodstein function \(G(n) \approx f_{\varepsilon_0}(n)\)
*Bracket notation \(n\$[[0]_2] \approx f_{\varepsilon_0}(n)\)
*Hayden's Array Notation \(a (1 \# 1 \# \cdots \# 1 \# 1 , 1) b \approx f_{\varepsilon_0}(n)\) (limit)
*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)
*Pound-Star Notation \(\approx f_{\varepsilon_0}(n)\) (limit)
*Circle(n) function \(\approx f_{\varepsilon_0}(n)\)
*m(n) map \(\approx f_{\varepsilon_0}(n)\)
*Hydra(n) function \(\approx f_{\varepsilon_0}(n)\)
*Worm(n) function \(\approx f_{\varepsilon_0}(n)\)
*Primitive sequence system \(\approx f_{\varepsilon_0}(n)\)
*Marxen.c function \(h(g(n),n)\) (upper bound) \(\approx f_{\varepsilon_0 2}(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)\) (limit)
*Three Bracket NaN \(\approx f_{\varphi(\omega,0)}(n)\)
== 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.
The fast-growing hierarchy here below the Small Veblen ordinal is given using Veblen function and beyond that we use Buchholz's function and Extended Buchholz's function. Beyond the Countable limit of Extended Buchholz's function, we use the tautological norm on the ordinal notation associated to Rathjen's psi for expressions including the function. On the other hand, \(\psi\) with inputs larger than \(\varepsilon_{\Omega_{\omega}+1}\) with respect to Buchholz's function (or \(\Omega_{\Omega_{._{._.}}}\) with respect to Extended Buchholz's function) in estimations are unspecified (and possibly ill-defined) OCFs, and hence those estimations are meaningless. Also, these estimations are not necessarily verified, and could be simply expectations, i.e. conjectural one without proofs.
*Fusible margin function \(m_1(x)\) (A non-trivial description of the conjectural growth rate is unknown.)
*Extended Cascading-E Notation Ea#^^^^......^^^#b \(\approx f_{\varphi(\omega,0,0)}(n)\) (limit)
*Hyper-Extended Cascading-E Notation Ea#{#{#{...{#{#}#}...}#}#}#b \(\approx f_{\varphi(1,0,0,0)}(n)\) (limit)
*Extended Q-supersystem \(xQ_{\underbrace{1,0,0,\ldots,0,0}_{n}}(n) \approx f_{\psi_0(\Omega^{\Omega^{\omega}})}(n)\) (limit)
*Weak tree function \(> f_{\psi_0(\Omega^{\Omega^{\omega}})}(n)\) (More precisely, the strict lowerbound is proved for tree(1.00001n+2) rather than tree(n).)
*TREE(n) function \(\approx f_{\psi_0(\Omega^{\Omega^{\omega}\omega})}(n)\)
*Hyperfactorial array notation (dimensional and "nested" arrays) \(\approx f_{\psi_0(\Omega^{\Omega^{\Omega}})}(n)\) (limit)
*Collapsing-E Notation Ea#{&^&^&^&^... ...}#b \(\approx f_{\psi_0(\varepsilon_{\Omega+1})}(n)\) (limit)
*Bird's H(n) function \(\approx f_{\psi_0(\varepsilon_{\Omega+1})}(n)\)
*Bird's S(n) function (original) \(\approx f_{\vartheta(\theta_1(\Omega))}(n)\) 
*Bird's U(n) function \(\approx f_{\psi_0(\Omega_\omega)}(n)\)
*Pair sequence system \(\approx f_{\psi_0(\Omega_\omega)}(n)\)
*Hyper primitive sequence system \(\approx f_{\psi_0(\Omega_{\omega})}(n)\)
*段階配列表記 \(\approx f_{\psi_0(\Omega_{\omega})}(n)\)
*SCG(n) function \(\geq f_{\psi_0(\Omega_\omega)}(n)\) 
*BH(n) function \(\approx f_{\psi_0(\varepsilon_{\Omega_\omega + 1})}(n)\) 
*Bird's array notation \(\approx f_{\psi_0(\Omega_\Omega)}(n)\) (limit)
*Bird's S(n) function (new definition) \(\approx f_{\psi_0(\Omega_\Omega)}(n)\)
*Hyperfactorial array notation \(\geq f_{\psi_0(\varepsilon_{\Omega_\omega+1})}(n)\) with respect to Buchholz's function or \(\geq f_{\psi_0(\Omega_{\Omega_{...} })}(n)\) with respect to Extended Buchholz's function
*降下段階配列表記 \(\approx f_{\psi_{\chi_0(0)}(\Phi_1(0))}(n)\) with respect to Rathjen's ψ = \(f_{\psi_0(\Omega_{\Omega_{...} })}(n)\) with respect to Extended Buchholz's function
*Dollar function (Extended Bracket notation) \(\approx f_{\psi_{\chi_0(0)}(\Phi_1(0))}(n)\) (expected limit)
*Bird's array notation (Douglas Shamlin Jr.'s extension)https://www.youtube.com/watch?v=CiGO3u3wgTE&t=300shttps://www.youtube.com/playlist?list=PLUp0pAa9wfYBpZv4tb58qPm_7XLvkzdOY \(\approx f_{\psi_{\chi_0(0)}(\Phi_1(0))}(n)\) (expected limit)
*Hayden's Extended Array Notation \(\approx f_{\psi_{\chi_0(0)}(\Phi_1(0))}(n)\) (expected limit)
*KumaKuma ψ function \(\approx f_{\psi_{\chi_0(0)}(\psi_{\chi_{3}(0)}(0))}(n)\)
*多変数段階配列表記 \(\approx f_{\psi_{\chi_0(0)}(\psi_{\chi_{\omega}(0)}(0))}(n)\)
*ε function \(\approx f_{\psi_{\chi_0(0)}(\chi_{M+1}(0))}(n)\)
*Naruyoko is the great (A non-trivial description of the conjectural growth rate is unknown.)
*Stegert's \(f\) functions (limit)
*Bashicu matrix system (A non-trivial description of the conjectural growth rate is unknown, but it is believed to be strong.)
*N primitive (A non-trivial description of the conjectural growth rate is unknown, but it is believed to be strong.)
*Y sequence (A non-trivial description of the conjectural growth rate of the desired behaviour is unknown, but it is believed to be strong.)
*ω-Y sequence (A non-trivial description of the conjectural growth rate of the desired behaviour is unknown, but it is believed to be strong.)
*Loader.c function \(D(n)\) (A non-trivial description of the conjectural growth rate is unknown, but it is believed to be strong.)
== Stronger set theories ==
These functions cannot be proven total in \(\textrm{ZFC}\), but are known to be provably total in stronger set theories.
*Friedman's finite promise games functions \(\textrm{FPLCI}(a)\), \(\textrm{FPCI}(a)\), and \(\textrm{FLCI}(a)\) defined in \(\textrm{SMAH}^+\)
*Greedy clique sequence functions \(\textrm{USGCS}(k)\), \(\textrm{USGDCS}(k)\), \(\textrm{USGDCS}_2(k)\), and \(\textrm{USGDCS}_2(n)\) defined in \(\textrm{HUGE}^+\)
*Friedman's finite trees function \(F(k,p)\) defined in \(\textrm{ZFC}\) augmented by the axiom "for any \(k \in \mathbb{N}\), there exists a \(k\)-subtle cardinal"
*Laver's function \(q(n)\) defined in \(\textrm{ZFC}+\textrm{I}3\)
*I0 function \(\textrm{I}0(n)\) defined in \(\textrm{ZFC}+\textrm{I}0\) augmented by its own \(\Sigma_1\)-soundness.
== 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
*\(b_k(N)\) function using Betti numbers.
*Doodle function
*Xi function
*Infinite time Turing machine busy beaver function
*Rayo's function (A problem on axioms has been pointed out.)
*FOOT (A problem on its definition has been pointed out.)
*\(f\), from First Order Theory beyond Higher Order Set Theory (well-definedness of this function is currently not yet justified)
== 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 literally uncomputable with transfinite indices, 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.
*Bowers' Exploding Array Function (BEAF). BEAF is not formalized and well-defined beyond tetrational arrays, so there are multiple interpretations by other googologists than the creator. A conjectural growth rate of a desired interpretation heavily depends on analysts.
*Strong array notation (SAN). SAN is not formalized, so there are multiple interpretations by other googologists than the creator. A conjectural growth rate of a desired interpretation corresponds to C(C(Ω22+C(Ω2+C(C(Ω2,C(Ω2,C(Ω22,0))),C(Ω2,C(Ω22,0))),0),0),0)Hyp cos, https://stepstowardinfinity.wordpress.com/2016/08/27/pdan_vs_ton/ in Taranovsky's ordinal notation using Hyp_cos's fundamental sequences, but there is no actual proof.
*Username5243's Array Notation (UNAN). The original definition of UNAN is ill-defined due to domain-related issues. The creator's expectation of the limit of the notation (assuming that UNAN is well-defined) is approximately \(f_{\Gamma_0}(n)\) in the website. In addition, the creator also continued to extend the notation beyond dimensional first-order array notation level to beyond nested array subscripts (see introduction and analysis of UNAN from basic array notation level to array subscript notation level here), which its limit is expected to reach the fast-growing hierarchy ordinal level of the countable limit of Extended Buchholz's function (\(>f_{\psi_0(\Omega_{\Omega_{...}})}(n)\)).
*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.
*TR function. It is a hierarchy of functions indexed by formal theories, or a function on the pair of a formal theory and a natural number.
*Revised Pehan Notation
== References ==
es:Lista de funciones
fr:Liste des fonctions
ja:関数の一覧
zh:函數列表
 
Category:Lists