Graham's number: Difference between revisions

From BusyBeaverWiki
Jump to navigation Jump to search
VisualWikitext
Created page with "'''Graham's number''' (<math>g_{64}</math> or <math>G</math>) 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 <math>n</math> such that <math>BB(n) > g_{64}</math>. There is an active search for the s..."
 
C7X (talk | contribs)
117 edits
Correction
 
(7 intermediate revisions by 2 users not shown)
Line 5: Line 5:
<math display="block">
<math display="block">
\begin{array}{l}
\begin{array}{l}
   g_0 & = & 4 \
   g_0 & = & 4 \\
   g_n & = & 3 \uparrow^{g_{n-1}} 3 & \text{if } n \ge 1
   g_n & = & 3 \uparrow^{g_{n-1}} 3 & \text{if } n \ge 1 \\
\end{array}
\end{array}
</math>
</math>
Line 14: Line 14:
Using the [[fast-growing hierarchy]], <math>g_{64} < f_{\omega + 1}(64)</math>.
Using the [[fast-growing hierarchy]], <math>g_{64} < f_{\omega + 1}(64)</math>.


Let <math>N_G</math> be the smallest integer such that <math>BB(N_G) > g_{64}</math>.
Let <math>N_G</math> be the smallest integer such that <math>S(N_G) > g_{64}</math>.


== Bounds ==
== Bounds ==
The current known bounds for <math>N_G</math> are:
The current known bounds for <math>N_G</math> are:
<math display="block">
<math display="block">
   6 \le N_G \le 14
   6 \le N_G \le 13
</math>
</math>


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 <math> > f_{\omega + 1}(65\,536) > g_{64} </math> steps.
The lower bound comes from the proof that [[BB(5)]] = 47,176,870 and the upper bound from a specific 13-state TM found by 50_ft_lock in March 2026 which runs for <math> > f_{\omega + 1}(2\,047) > g_{64} </math> steps.


=== History of Graham-beating TMs ===
=== 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 [https://googology.fandom.com/wiki/Graham%27s_number#Comparison_with_busy_beaver_function Googologogy wiki], [https://cs.stackexchange.com/questions/69469/what-is-the-smallest-n-such-that-bbn-grahams-number/69476#69476 a 2017 CS Stack Exchange answer], [https://www.sligocki.com/2010/07/04/beating-grahams-number.html#results-from-the-future a 2022 history synthesis by Shawn Ligocki] and [https://bbchallenge.org/~pascal.michel/ha#topdown summary by Pascal Michel].
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 [https://googology.fandom.com/wiki/Graham%27s_number#Comparison_with_busy_beaver_function Googologogy wiki], [https://cs.stackexchange.com/questions/69469/what-is-the-smallest-n-such-that-bbn-grahams-number/69476#69476 a 2017 CS Stack Exchange answer], [https://www.sligocki.com/2010/07/04/beating-grahams-number.html#results-from-the-future a 2022 history synthesis by Shawn Ligocki] and [https://bbchallenge.org/~pascal.michel/ha#topdown 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 <math>\Sigma</math> function, but since <math>S(n) \ge \Sigma(n)</math> they apply to this formulation as well.
 
{| class="wikitable"
TODO: Add table
|+History of Graham-beating TMs
!States
!Date
!Discoverer
!Source
!Verification
|-
|91
|9 Sep 2010
|"res001"
|[https://morethanazillion.blogspot.com/2010/09/small-turing-machine-whose-output.html Blog Post]
|
|-
|72
|13 Sep 2010
|"res001"
|[https://morethanazillion.blogspot.com/2010/09/small-turing-machine-whose-output.html Blog Post]
|
|-
|64
|19 Sep 2010
|"res001"
|[https://morethanazillion.blogspot.com/2010/09/64-state-turing-machine-whose-output.html Blog Post] [https://web.archive.org/web/20130509222047/https://sites.google.com/site/res0001/surpassing-graham-s-number Summary]
|
|-
|25
|31 Mar 2013
|"Deedlit11"
|[https://googology.fandom.com/wiki/User_blog:Deedlit11/Okay,_more_Turing_machines#A_New_Record!_Beating_Graham's_number_with_a_2-symbol_TM Googology Post]
|
|-
|24
|27 September 2013
|"Wythagoras"
|[https://googology.fandom.com/wiki/User_blog:Deedlit11/Okay,_more_Turing_machines?commentId=4400000000000011880 Googology Comment]
|
|-
|23
|7 October 2013
|"Wythagoras"
|[https://googology.fandom.com/wiki/User_blog:Deedlit11/Okay,_more_Turing_machines?commentId=4400000000000011880&replyId=4400000000000036301 Googology Comment]
|
|-
|22
|5 August 2014
|"Wythagoras"
|[https://googology.fandom.com/wiki/User_blog:Wythagoras/NEWS!_I_found_a_22-state_machine_that_beats_G! Googology Post]
|
|-
|18
|24 Jul 2016
|"Wythagoras"
|[https://googology.fandom.com/wiki/User_blog:Wythagoras/The_nineteenth_Busy_Beaver_number_is_greater_than_Graham's_Number!?useskin=oasis Googology Post]
|
|-
|16
|26 Mar 2021
|Daniel Nagaj
|[https://googology.fandom.com/wiki/User_blog:Wythagoras/The_nineteenth_Busy_Beaver_number_is_greater_than_Graham%27s_Number!?commentId=4400000000000019187&replyId=4400000000000101283 Googology Comment] [http://morphett.info/turing/turing.html?197640ce0f380f8a6b0a4cdd138156a0 TM Definition]
|[https://www.sligocki.com/2022/07/11/bb-16-graham.html Analysis by Shawn Ligocki in 2022]
|-
|14
|17 Aug 2024
|[[User:Racheline|Racheline]]
|[https://discord.com/channels/960643023006490684/960643023530762341/1274366178529120287 Discord Message]
|
|-
|13
|13 March 2026
|50_ft_lock
|[https://discord.com/channels/960643023006490684/1331570843829932063/1481871400640839691 Discord Message]
|}

Latest revision as of 18:36, 14 March 2026

Graham's number (g64 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)>g64. There is an active search for the smallest TM that runs for over Graham's number steps.

Definition

See Wikipedia article for more detail g0=4gn=3↑gn−13if n≥1

Graham's number is g64.

Using the fast-growing hierarchy, g64<fω+1(64).

Let NG be the smallest integer such that S(NG)>g64.

Bounds

The current known bounds for NG are: 6≤NG≤13

The lower bound comes from the proof that BB(5) = 47,176,870 and the upper bound from a specific 13-state TM found by 50_ft_lock in March 2026 which runs for >fω+1(2047)>g64 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 Σ function, but since S(n)≥Σ(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
24 27 September 2013 "Wythagoras" Googology Comment
23 7 October 2013 "Wythagoras" Googology Comment
22 5 August 2014 "Wythagoras" Googology Post
18 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
13 13 March 2026 50_ft_lock Discord Message
Retrieved from "https://wiki.bbchallenge.org/w/index.php?title=Graham%27s_number&oldid=6629"