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 $S(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. In general, these results are self-reported and we do not know of independent verification for most of them. Most of these were actually proven as bounds for the $\Sigma$ function, but since $S(n)\geq \Sigma (n)$ they apply to this formulation as well.

History of Graham-beating TMs

States	Date	Discoverer	Source	Verification
91	9 Sep 2010	"res001"	Blog Post
72	13 Sep 2010	"res001"	Blog Post
64	19 Sep 2010	"res001"	Blog Post Summary
25	31 Mar 2013	"Deedlit11"	Googology Post
19	24 Jul 2016	"Wythagoras"	Googology Post
16	26 Mar 2021	Daniel Nagaj	Googology Comment TM Definition	Analysis by Shawn Ligocki in 2022
14	17 Aug 2024	Racheline	Discord Message