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. 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 exceedingly 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 index (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.

In cases where the index is not an integer, the representation usually represents an irrational number, though sometimes it can represent a rational number, or even an integer.

For example, $10^{7.67}$ represents the number 46,773,514.1287..., an irrational number, whereas $16^{6.75}$ represents the number 134,217,728, an integer.

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

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

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

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

When representing certain exceedingly large numbers using scientific notation, the index itself may also be represented using scientific notation.

$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}1,& \text{if }b=0\\ a^b,& \text{if }n=1\\ 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$

In popular mathematics, Graham's number ($=g_{64}$) is represented using the following recursive function involving 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{otherwise.}\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 further, stronger diagonalizations across fast-growing functions. Functions under the fast-growing hierarchy are written in the form $f_{\alpha }(n)$, and may be 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.)

The fast-growing hierarchy requires a defined set of fundamental sequences; the fundamental sequence of a limit ordinal $\alpha$ consists of an ordered 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) 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

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({\mathrm{\Omega }}_{\omega })$.

The proof theoretic ordinal of second order arithmetic is unknown (relative to any ordinal notation), but 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 gives way to the fast growing function $D(n)$ (defined by Ralph Loader in 2003 to create the eponymous Loader's number = $D^5(99)$), which computes something similar to (but larger than) "The largest number that is a minimal x where the statement $\varphi (x)$ is true, and where $\mathrm{\exists }x\varphi (x)$ can be written in less than n symbols and shown to be true in CoC." $D(n)$ outgrows all functions definable 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 }(1850)>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}$ cardinals, 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