Graham's number

Graham's number ($g_{64}$ or $G$) is a famously huge number which Martin Gardner claimed was the "largest number ever used in a serious mathematical proof" in 1977. Since it is one of the most famous large numbers, it has become a bit of a yardstick for measuring "hugeness". In the specific context of the Busy Beaver game, we can ask, what is the smallest $n$ such that $BB(n)>g_{64}$. There is an active search for the smallest TM that runs for over Graham's number steps.

Definition

See Wikipedia article for more detail Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{array}{l} g_0 & = & 4 \ g_n & = & 3 \uparrow^{g_{n-1}} 3 & \text{if } n \ge 1 \end{array} }

Graham's number is $g_{64}$.

Using the fast-growing hierarchy, $g_{64}<f_{\omega +1}(64)$.

Let $N_{G}$ be the smallest integer such that $BB(N_{G})>g_{64}$.

Bounds

The current known bounds for $N_{G}$ are:

$$6\leq N_{G}\leq 14$$

The lower bound comes from the proof that BB(5) = 47,176,870 and the upper bound from a specific 14-state TM found Racheline in August 2024 which runs for $>f_{\omega +1}(65\,536)>g_{64}$ steps.

History of Graham-beating TMs

There is no one authoritative source on the history of TMs beating Graham's number. Most were posted in personal blog posts, Googology pages/comments or on the bbchallenge Discord. They are often unverified and sometimes undocumented. This list is based upon historical accounts listed on Googologogy wiki, a 2017 CS Stack Exchange answer, a 2022 history synthesis by Shawn Ligocki and summary by Pascal Michel.

TODO: Add table