Measuring large numbers

The busy beaver functions are known to grow faster than any computable function, as do many of their variants. Because of this, values of the function, or lower bounds on the function can be very, very large, so it is tempting to find ways of representing these numbers; this article will cover these methods.

Paradoxically, although the Kolgomorov complexity of stating "The runtime of program X" to define the runtime of program X is typically very low, it is often not useful as it does not give us good information on the size of the number. Informally, more "natural" or "combinatorial" ways of measuring large numbers are desired which allow us to relatively compare the rough "ballparks" of the numbers' scales. Tools like Knuth's up-arrow notation can help us achieve this, as well as more powerful methods such as fast-growing hierarchy or the diagonalization of an axiomatic foundation of mathematics.

Scientific notation

Scientific notation is one of the most common ways of representing large numbers; numbers written in standard scientific notation symbolically consist of a multiplicand (taking a value between 1 and the base, though is sometimes omitted), a base (commonly 10) and an exponent (usually an integer, though sometimes takes non-integer values if the multiplicand is omitted).

For example, $8.68\cdot 10^6$ represents the number 8,680,000, whereas $6.022\cdot 10^{23}$ represents the number 602,200,000,000,000,000,000,000. These numbers are often approximations (to some number of digits) or lower/upper bounds on the precise integer.

Non-integer exponents are also often used to approximate. For example, $10^{7.67}$ representing a lower bound for the number 46,773,515.

Certain busy beaver values can most conveniently be represented using scientific notation; they include:

$S(3,3)>1.1912\cdot 10^{17}$

$\mathrm{BBf}(23)>4.3932\cdot 10^{124}$

$\mathrm{B}\mathrm{B}\mathrm{\lambda }(38)>1.0017\cdot 10^{19,729}$

When representing even larger numbers using scientific notation, the exponent itself may also be represented using scientific notation. For example:

$S(2,5)>10^{10^{10^{3,314,360}}}$

Knuth's up-arrow notation

Knuth's up-arrow notation extends the sequence of recursive operators (i.e. addition, multiplication, exponentiation) to higher-order functions (e.g. tetration, pentation) which grow much more rapidly.

Tetration, the operation following exponentiation in the sequence of "hyperoperators" is defined by:

$a\uparrow \uparrow b=\{\begin{array}{ll}1,& \text{if }b=0\\ a^{a\uparrow \uparrow (b-1)},& \text{otherwise.}\end{array}$

The lower bound for $S(2,5)$ can thus be more concisely (though more weakly) written as $S(2,5)>10\uparrow \uparrow 4$.

Knuth's up-arrow notation generalizes this though the following formula (where an arrow with a superscript of n represents the operator indicated by n arrows):

$a{\uparrow }^{n}b=\{\begin{array}{ll}{a}^b,& \text{if }n=1,\\ 1,& \text{if }n>1\text{ and }b=0,\\ a{\uparrow }^{n-1}(a{\uparrow }^n(b-1)),& \text{otherwise.}\end{array}$

Larger busy beaver values represented using Knuth's up-arrow notation include:

$S(2,6)>10\uparrow \uparrow \uparrow 3$

$S(4,3)>10\uparrow \uparrow \uparrow \uparrow 4$

$S(3,4)>2{\uparrow }^{15}3$

$S(3,5)>2{\uparrow }^{2{\uparrow }^{15}3}3$

bbchallenge uses a piecewise extension of tetration in order to write numbers of this scale more accurately:

$a\uparrow \uparrow b=\{\begin{array}{ll}b+1,& \text{if }-1<b\le 0,\\ a^{a\uparrow \uparrow (b-1)},& \text{otherwise.}\end{array}$

Note that when using this method, the function $10\uparrow \uparrow x$, and other functions similar to it, are not analytic functions; however, that requirement is unnecessary when using this method to represent large numbers. Additionally, methods of obtaining analytic hyperoperators are complex, typically involving Abel functions, Riemann mappings, or Jabotinsky matrices; this method forgoes this, allowing for the ease of calculation.

In this format, the lower bound for $S(2,5)$ can be written more precisely as $S(2,5)>10\uparrow \uparrow 4.8142$.

Graham's number ($g_{64}$) is a famously large number that is defined using Knuth's up-arrow notation:

$g_n=\{\begin{array}{ll}3\uparrow \uparrow \uparrow \uparrow 3,& \text{if }n=1\\ 3{\uparrow }^{g_{n-1}}3,& \text{if }n>1\end{array}$

The Ackermann function $\mathrm{A}(n,n)$ grows at roughly the same rate as $2{\uparrow }^{n}3$. It can be said to "diagonalize" across the hyperoperators, eventually dominating every single hyperoperator.

Fast-growing hierarchy

The fast-growing hierarchy uses the fundamental sequences of ordinals to define diagonalizations across previous functions in the hierarchy. Functions in the fast-growing hierarchy are written in the form $f_{\alpha }(n)$, and are calculated according to three rules:

$f_0(n)=n+1$

$f_{\alpha +1}(n)=f_{\alpha }^n(n)$

$f_{\alpha }(n)=f_{\alpha [n]}(n)$ where $\alpha$ is a limit ordinal (i.e. not a successor of any ordinal, nor zero.)

Usually, an ordinal $\lambda$ is first chosen, and then $f_{\alpha }$ is defined via to the clauses above for all ordinals $\alpha <\lambda$. This requires a system of fundamental sequences to be fixed first, where for each limit ordinal $\alpha <\lambda$ the fundamental sequence of $\alpha$ is a sequence of ordinals which has a supremum of $\alpha$.

It is suspected that in this wiki, and in most other spaces that deal with googology, the fundamental sequences described by Maksudov (2017)^{[citation needed]} are used to define the fast-growing hierarchy.

In this manner, the value of $S(3,5)$ can be more concisely (though more weakly) written as $S(3,5)>f_{\omega }(2{\uparrow }^{15}3)$.

Other busy beaver values that necessitate the use of the fast-growing hierarchy include:

$\mathrm{B}\mathrm{B}\mathrm{\lambda }(49)>f_{\omega +1}\left(\frac{2\uparrow \uparrow 6}{2}\right)$

$\mathrm{S}(51)>f_{{\epsilon }_0+1}(8)$

$\mathrm{B}\mathrm{B}\mathrm{\lambda }(100)>f_{{\psi }_0({\mathrm{\Omega }}_{\omega })+1}(4)$

Defining fundamental sequences: ordinal notations and ordinal collapsing functions

Individually defining fundamental sequences for a transfinite number of ordinals may be less than ideal; thus, to define the fast-growing hierarchy effectively, ordinal notations, which define a computable mapping between sequences of symbols and ordinals can be used to define fundamental sequences instead. TODO

Comparing FGH and BB

Ordinal α	Least m that BB(m) confirmed >= fα(2)	Least m that BB(m) confirmed >= fα(3)	Least m that BB(m) confirmed >= fα(10)
$\omega$ (Cantor normal form)	3	6	7
$\omega +1$	7	8	10
$\omega +2$	10	12	12
$\omega \times 2$	10	14	20
${\omega }^2$	10	20	21
${\omega }^{\omega }$	10	29	31
${\omega }^{\omega }+1$	31	31	31
${\epsilon }_0$ (Epsilon ordinals)	10	31	51
$\phi (\omega ,0)$ (Veblen's phi function)
${\psi }_0({\mathrm{\Omega }}_2)$ (Buchholz's psi function)
${\psi }_0({\mathrm{\Omega }}_{\omega })$
${\psi }_0({\epsilon }_{{\mathrm{\Omega }}_{\omega }+1})$
${\psi }_0({\mathrm{\Omega }}_{{\mathrm{\Omega }}_{{\mathrm{\Omega }}_{...}}})$
$lim(BMS)$ (Bashicu matrix system)			150

Theories

The proof-theoretic ordinal of a theory is defined as supremum of the order types of all ordinal notations that can be shown to be well-founded within the theory.

Some examples of proof theoretical ordinals include $\mathrm{PTO}(Q)=\omega$, $\mathrm{PTO}(PA)={\epsilon }_0$, and $\mathrm{PTO}(\mathrm{KP})={\psi }_0({\epsilon }_{\mathrm{\Omega }+1})$. Here Q is Robinson arithmetic, PA is Peano Arithmetic, and KP is Kripke-Platek set theory.

Determination of the proof theoretic ordinal of second order arithmetic has been claimed in two preprints, one of which is a work-in-progress, and is known to vastly exceed that of $\mathrm{KP}$.

They can be used to compare the strength of different theories, as well as (by definition) an indicator as to which ordinal notations (or functions that are derived from ordinal notations) cannot be shown to be well-founded (or total) in a theory.

A notable example of a theory which is directly used to create fast growing functions is the Calculus of Constructions (CoC), which has a proof-theoretic ordinal greater than that of any nth order arithmetic ($Z_n$); well-formed statements in CoC can also be easily detected, and are strongly normalizing (TODO: explain what that means in this context).

CoC yields the fast growing function $D(n)$ (defined by Ralph Loader in 2001 to create the eponymous Loader's number = $D^5(99)$), which computes something similar to (but larger than) "The largest number \(x\) such that there is a ${\mathrm{\Sigma }}_1^0$ formula $\varphi (x)$ such that $\varphi (x)$ is true and $\mathrm{\exists }x\varphi (x)$ is provable in CoC with a proof of length \(\leq \log_2 n\)". $D(n)$ outgrows all recursive functions provably total in $Z_{\omega }$; the growth rate of $D(n)$ is sometimes informally written as $f_{\mathrm{PTO}(Z_{\omega })}(n)$, though no fundamental sequence has yet been defined for all ordinals under $\mathrm{PTO}(Z_{\omega })$.

The simplicity of CoC and $D(n)$ has been utilized to show the following bounds for certain busy beaver values:

$\mathrm{B}\mathrm{B}\mathrm{\lambda }(1797)>D^5(99)$

$\mathrm{S}(1015)>D^5(99)$

An even stronger but simpler function, $q(n)$, has been derived from the structure of $\mathrm{I3}$ elementary embeddings, though it is unknown if this function can be shown to be total in $\mathrm{ZFC}$ alone, and whether it grows faster than the aforementioned $D(n)$. It is used in the following (conjectured) bounds:

$\mathrm{B}\mathrm{B}\mathrm{\lambda }(201)>q(5)$

$\mathrm{S}(67)>q^{81}(q(5)-2)$

Resources

The Googology wiki hosts good information on methods of describing large numbers or large upper bounds for numbers.

• https://googology.miraheze.org/wiki/Main_Page