https://scottaaronson.blog/?p=8972 Shtetl-Optimized The Blog of Scott Aaronson If you take nothing else from this blog: quantum computers won't solve hard problems instantly by just trying all solutions in parallel. Also, please read Zvi Mowshowitz's masterpiece on how to fix K-12 education! --------------------------------------------------------------------- << Raymond Laflamme (1960-2025) BusyBeaver(6) is really quite large For overdetermined reasons, I've lately found the world an increasingly terrifying and depressing place. It's gotten harder and harder to concentrate on research, or even popular science writing. Every so often, though, something breaks through that wakes my inner child, reminds me of why I fell in love with research thirty years ago, and helps me forget about the triumphantly strutting factions working to destroy everything I value. Back in 2022, I reported an exciting advance in BusyBeaverology: namely, whereas we previously knew merely that BB(6) > 10^36,534, Pavel Kropitz managed to show that BB(6) > ^1510. For those tuning in from home, here BB(6) is the 6^th Busy Beaver number, i.e. the maximum number of steps that a 6-state Turing machine with a {0,1} alphanet can take before halting, when run on an initially all-0 input tape. Also, the left-superscript means tetration, or iterated exponentiation: for example, ^1510 means 10 to the 10 to the 10 and so on 15 times. By comparison, last year the international "BBchallenge" team determined that BB(5) is "merely" 47,176,870 (see also Quanta magazine's superb feature article on that milestone). So, between 5 and 6 is where the Busy Beaver function makes its leap, from the millions to beyond the bounds of observable reality. But if you thought that was the end of the BB(6) story, think again! Eleven days ago, Tristan Sterin, who organized the BBchallenge the team, emailed to tell me that a team member with the handle "mxdys" improved the BB(6) bound yet further, to BB(6) > ^10,000,00010 (i.e., 10 to the 10 to the 10 and so on 10 million times), with a correctness proof in Coq. Then, three days ago, Tristan wrote again to say that mxdys has improved the bound again, to $$ BB(6) \gt ^{^{{^9}2}2}2 $$ I.e., BB(6) is at least 2 tetrated to the 2 tetrated to the 2 tetrated to the 9. So in particular, BB(6) is at least 2 pentated to the 5, where pentation is iterated tetration, i.e. the operation that is to tetration as tetration is to exponentiation, exponentiation is to multiplication, and multiplication is to addition. Last week, when we "merely" knew that BB(6) > ^10,000,00010, I talked to a journalist who asked me to give an intuitive sense of how big such a number is. So I said, imagine you had ^10,000,00010 grains of sand. Then you could ... well, uh ... you could fill about ^10,000,00010 copies of the observable universe with that sand. I hope that helps people visualize it! The journalist also asked: have these new discoveries about BB(6) caused me to rethink any broader beliefs about the Busy Beaver function? And I mean, yes and no: it was always completely within the realm of possibility that BB(6) would already be, not some puny little thing like 10^36,534, but way out in iteration land. Now that we know for sure that it is, though, maybe I ought to conjecture that the value of BB(n) becomes independent of the ZFC axioms of set theory already when n is 7 or 8 or 9, rather than when it's 20 or 30 or whatever. (Currently, we know that BB(n) becomes independent of ZFC only when n=643.) --------------------------------------------------------------------- Unrelated Update: I'm just now returning to the US from STOC'2025 in Prague, where I saw lots of old friends and learned many interesting new things, again helping to distract me from the state of the world! Many I'll write about some of those things in a future post. For now, though, anyone who's interested in my STOC plenary lecture, entitled "The Status of Quantum Speedups," can check out the PowerPoint slides here. Email, RSS Follow This entry was posted on Saturday, June 28th, 2025 at 11:21 am and is filed under Announcements, Nerd Interest. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site. 32 Responses to "BusyBeaver(6) is really quite large" 1. Vladimir Says: Comment #1 June 28th, 2025 at 12:12 pm I eagerly await the day when you'll stop listing "Physics simulations" under "In-Principle Quantum Advantage". 2. Matus Says: Comment #2 June 28th, 2025 at 12:19 pm > Now that we know for sure that it is, though, maybe I ought to conjecture that the value of BB(n) becomes independent of the ZFC axioms of set theory already when n is 7 or 8 or 9, rather than when it's 20 or 30 or whatever. Why is that? There are many more countable big numbers. 3. Joshua Zelinsky Says: Comment #3 June 28th, 2025 at 12:31 pm "maybe I ought to conjecture that the value of BB(n) becomes independent of the ZFC axioms of set theory already when n is 7 or 8 or 9" Why not be even bolder at this point and conjecture that BB(6) is independent of ZFC? 4. Scott Says: Comment #4 June 28th, 2025 at 12:33 pm Vladimir #1: Why? 5. Joshua Zelinsky Says: Comment #5 June 28th, 2025 at 12:38 pm @Matus #2, "Why is that? There are many more countable big numbers." We already know that BB(745) is independent of ZFC. But more importantly, we know that one of the ways things can get to be independent of some reasonably tame axiomatic system is if they involve an extremely fast growth. This is thematically similar to that. Also, this is evidence that there are Turing machines with very few states which don't halt until extremely largely iterations when run on the blank tape, which makes it more plausible that there are some machines whose halting or lack thereof is not easily quantifiable in something like ZFC since it suggests that there's just a lot of really complicated machines that have a small number of states. 6. Scott Says: Comment #6 June 28th, 2025 at 12:41 pm Matus #2: Truthfully I have no idea. But wherever I previously believed independence happened, it seems like I ought to adjust downwards. 7. Scott Says: Comment #7 June 28th, 2025 at 12:42 pm Joshua Zelinsky #3: Oh, I left that bolder conjecture for a commenter like you to make! 8. Sniffnoy Says: Comment #8 June 28th, 2025 at 12:52 pm (Currently, we know that BB(n) becomes independent of ZFC only when n=745.) According to your own post from a year ago, it's down to 643! I really wish the BBChallenge people kept better track of this stuff, I have tried to follow along to some extent but they rare update the main website, and the newer faster-updating wiki is confusingly organized... and on this particular question it has no information at all, just this little stub. Gotta say the Mario 64 A-button challenge people have done a much better job of this sort of thing. 9. Ajay Says: Comment #9 June 28th, 2025 at 1:09 pm > imagine you had ^10,000,00010 grains of sand. Then you could ... well, uh ... you could fill about ^10,000,00010 copies of the observable universe with that sand. Since they are the same number, wouldn't this mean that each copy of the observable universe has exactly one grain of sand in it? Is this a typo? 10. Scott Says: Comment #10 June 28th, 2025 at 1:12 pm Sniffnoy #8: [forehead slap] I'd totally forgotten, thanks!!! Just updated the post. 11. Vladimir Says: Comment #11 June 28th, 2025 at 1:44 pm Scott #4 As I've repeatedly failed to convince you but hope someone someday yet will, there's certainly a known in-principle advantage for unitarily evolving a given initial state, but not for actually finding an interesting initial state, e.g. the ground state of the Hubbard model or some large molecule. The latter is what most condensed matter physicists and quantum chemists think of as "physics simulations". 12. Edan Maor Says: Comment #12 June 28th, 2025 at 2:08 pm Interesting! How does BB(6) compare to other really large numbers at this stage? I assume it's still not the "largest" named number, but I'm not sure what actually is at this stage. I usually go with Rayo's number in my head. Question for Scott (or anyone): I've been brushing up on my basic set theory, and I think I've learned enough at this stage to ask - what do I need to learn to understand the proof of BB(745) (or anything else) being independent of ZFC? I want to understand this formally. Is basic Set Theory enough? 13. gwern Says: Comment #13 June 28th, 2025 at 2:11 pm I apologize if this is already answered in the links, but is there any insight into how the explosion is *so* large by adding a single more? What widget or computation are the 6s capable of expressing which can blast so far past 47,176,870? If they are just doing Collatz-like computations, what accounts for the growth there? (I know it's just a bound here, so you can't answer this question for *the* busy beaver, but I assume there are many longer programs, and it is not the case that all of the BB(6)s do less than or equal to 47,176,870 but then there is one pathological TM which does the headline 'at least 2 pentated to the 5'; and so you could relatively easily find a specific instance of a BB(6) which does, say, 47 billion instead of a mere 47 million, and analyze it to try to see what trick it is using. If that is not possible, why not?) 14. Scott Says: Comment #14 June 28th, 2025 at 2:17 pm Ajay #9: It breaks my heart to explain the joke, but ... ^ 1000000010 is so incomprehensibly more enormous than 10^100, or whatever your bound for the number of sand grains that could fit in the observable universe, that even after you divide the former by the latter, you still get a number that's most easily approximated as ^1000000010 (try it and see!). 15. Oscar Says: Comment #15 June 28th, 2025 at 2:20 pm Ajay #9. No, this is correct. The point is that tetration is fast enough that the number of universes is dramatically more than 999999910 (since this number is more than 999999910 times smaller than 1000000010) 16. Scott Says: Comment #16 June 28th, 2025 at 2:22 pm Vladimir #11: Oh, ok, that. One issue is that I talk pretty often to quantum chemists and material scientists who are engaged with this topic and who are much more optimistic about quantum speedups than you. In any case, though, "quantum simulations" very explicitly includes dynamical problems (eg reaction rates), not just properties of ground states where getting a quantum speedup that matters in practice will indeed be harder. 17. Vladimir Says: Comment #17 June 28th, 2025 at 2:30 pm Scott #16 I'm not pessimistic about quantum computers being useful for physics and chemistry in practice, just pedantic about claiming they have a known in-principle advantage in the same sense that Shor's algorithm has one. 18. Michael Dickens Says: Comment #18 June 28th, 2025 at 2:32 pm It's known that BB(14) is bigger than Graham's number, but this new finding leads me to believe that BB(7) is probably bigger than Graham's number. Intuitively, the technology required to go from pentation to Graham's number feels simpler than the technology required to go from `47,176,870` to `2 5`. 19. Scott Says: Comment #19 June 28th, 2025 at 2:33 pm Edan Maor #12: The new lower bound on BB(6) is still tiny compared to Graham's number, although huge compared to Skewes' number. I don't accept that "Rayo's number" is actually well-defined, since Rayo's definition depends on second-order logic--and hence, on which transfinite sets "really exist" and which don't, potentially even on questions like AC and CH. For BB(643) being independent of ZFC, conceptually there's almost nothing to understand. You just build an explicit 643-state Turing machine M that (very slowly) enumerates all the theorems of ZFC, halting if and only if it finds a contradiction. If ZFC could determine the value of BB(643), it could also prove that M ran for more steps than that and hence forever, thereby proving that ZFC is consistent, which would contradict the Second Incompleteness Theorem. Where you need to work your ass off and invent all sorts of tricks is just to reduce the number of states (a naive construction will have millions of states). For more see Riebel's thesis, which I linked in the post, or my paper with Adam Yedidia. 20. Scott Says: Comment #20 June 28th, 2025 at 2:36 pm Vladimir #17: If you really want to be pedantic, I'm going to out-pedant you by pointing out that "physics simulation" includes, as one special case, simulating a quantum computer running Shor's algorithm. 21. .mau. Says: Comment #21 June 28th, 2025 at 2:49 pm @scott#19: Thanks, I was just asking what it meant that BB(n) becomes independent of the ZFC axioms. 22. Scott Says: Comment #22 June 28th, 2025 at 2:54 pm .mau. #21: It means that there's no proof in ZFC of any statement of the form "BB(n)=k," for any explicit positive integer k. 23. Former Student Says: Comment #23 June 28th, 2025 at 2:55 pm Hi Scott, This is cool! When these improved bounds were found, was it a new machine being discovered each time, or the runtime analysis was improved? Was it all collatz like iterations that stop by chance, or some new ideas involved with the new discoveries? I know you talked about a machine that almost certainly doesn't halt statistically but hard to prove (some growing sequence needing to have more than twice as many evens than odds or something like that). Do we know of any machine that almost certainly does halt statistically but really hard to prove that it does (maybe because its pseudo-random sequence grows so fast, that it's hard to calculate the iteration at which it will halt?) 24. Jacker Says: Comment #24 June 28th, 2025 at 3:01 pm Ajay #9 > you could fill about The joke is in the "about" the same number, in relative terms. Because BB(6) is so large compared to the number of sand grains in the universe, you can easily say BB(6) times that number is about the same as BB(6). 25. Scott Says: Comment #25 June 28th, 2025 at 3:07 pm gwern #13: At a very high level, the 5-state champion does a Collatz-like iteration that happens to halt after a dozen or two steps, having expended ~47 million steps in doing so (the number of steps growing quadratically with the positive integers that are generated). As of a few days ago, the 6-state champions again did Collatz-like iterations that happen to halt after a bunch of steps. But now, each step of the iteration involves exponentiating the number from the previous step, which is how you quickly generate stacked exponentials. I don't understand yet how mxdys's most recent 6-state champion gets from there to pentation. Maybe you or someone else would like to look at the github and explain it to us! 26. Warner Losh Says: Comment #26 June 28th, 2025 at 3:39 pm Pretty soon we'll see that BB(6) is > [?][?] -1 but < [?][?]. And yes, I know. This is a joke... 27. Aron Says: Comment #27 June 28th, 2025 at 4:08 pm Hi Scott, I'm pretty interested in the use of quantum computers for drug discovery. However, I recently watched a video by Looking Glass Universe (https://www.youtube.com/watch?v=pDj1QhPOVBo&t=877s) in which she mentioned a paper written a while ago by Garnet Chan et al which seemed to indicate that for most generic chemical systems, (so nothing extremely strange that's fully correlated like superconductors), it is unlikely to get an exponential quantum advantage. From what I understand, this is because you need to already have a very good approximation of the ground state to get the ground state energy, and if this is the case it means a classical computer can probably already simulate the problem well. As such, I just wanted to get your thoughts on how likely you think it is that quantum computers will have a significant impact in this area (drug discovery, medicine, biology etc..)? And if it's not through quantum phase estimation, how will they be of use? Is there still a lot that pure Hamiltonian simulation can do in this area? Also I see in your recently posted slides that you think that recent developments (Yamakawa-Zhandry) etc seem to indicate that there are a lot of quantum algorithms with quantum advantage out there that remain to be discovered. I guess my question just is....if you had to guess, would you say you think there is a greater chance than not that there is something "Shor/QPE/HHL like in usefuleness" still lurking out there that we haven't found yet? Or most of what remains to be found will be highly esoteric (some new cryptographic scheme, complex physics system etc...). 28. Nick Drozd Says: Comment #28 June 28th, 2025 at 4:56 pm ...maybe I ought to conjecture that the value of BB(n) becomes independent of the ZFC axioms of set theory already when n is 7 or 8 or 9, rather than when it's 20 or 30 or whatever. Yes! All developments since 2020 point overwhelmingly in the direction of stronger conjectures. For example, one of the conjectures says something about when 2^BB(N) ^BB(5)2! 29. amohr Says: Comment #29 June 28th, 2025 at 5:06 pm Great post! Just wanted to point out a small typo, "expenentiation". Cheers! 30. Shawn Ligocki Says: Comment #30 June 28th, 2025 at 5:15 pm #13 To expand on Scott's comment, all 4 of these champions and former champions described here have the same basic structure: compute some big function, apply a collatz-like test, if one of the remainders, halt, otherwise repeat. As Scott mentioned, for the BB(5) champ that function is multiplication and for Pavel's 10||15 TM it is exponentiation. For the newest pentation TM, it is tetration. So it applies a tetration function several times and thus gets this low pentation level of iteration. Of course, the next question you may ask is, how are they computing these helper functions (multiplication, exponentiation, tetration)? The main method here is just loops. TMs can very easily add, do that over a loop and you get multiplication, do that over a loop and you get exponentiation, etc. This is how Pavel's 10||15 TM worked as well. The two newest champions take advantage of a slightly different technology we have called "Shift Overflow Counters". The basic idea is that they go through phases where they repeatedly increment a binary counter on the tape until it "overflows" (expands to require an extra digit). At those points it does a new behavior. This shift overflow counter technology roughly computes exponential functions (because binary counters take exponential steps to expand). With one extra loop on top of this you get a tetration level helper function. 31. Scott Says: Comment #31 June 28th, 2025 at 5:45 pm amohr #29: Thanks! Fixed. 32. Scott Says: Comment #32 June 28th, 2025 at 5:47 pm Shawn Ligocki #30: Thanks so much; that's extremely helpful! Leave a Reply You can use rich HTML in comments! You can also use basic TeX, by enclosing it within $$ $$ for displayed equations or \( \) for inline equations. Comment Policies: After two decades of mostly-open comments, in July 2024 Shtetl-Optimized transitioned to the following policy: All comments are treated, by default, as personal missives to me, Scott Aaronson---with no expectation either that they'll appear on the blog or that I'll reply to them. At my leisure and discretion, and in consultation with the Shtetl-Optimized Committee of Guardians, I'll put on the blog a curated selection of comments that I judge to be particularly interesting or to move the topic forward, and I'll do my best to answer those. But it will be more like Letters to the Editor. Anyone who feels unjustly censored is welcome to the rest of the Internet. To the many who've asked me for this over the years, you're welcome! [ ] Name (required) [ ] Mail (will not be published) (required) [ ] Website [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [Submit Comment] [ ] [ ] [ ] [ ] [ ] [ ] [ ] D[ ] --------------------------------------------------------------------- Shtetl-Optimized is proudly powered by WordPress Entries (RSS) and Comments (RSS).