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 (unknown function "\begin{array}"): {\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