16 ms·

BusyBeaver(6) Is Quite Large

272 points by bdr 1y ago

seeknotfind 1y ago
> So I said, imagine you had 10,000,000sub10 grains of sand. Then you could … well, uh … you could fill about 10,000,000sub10 copies of the observable universe with that sand. I don't get this part. Is it really rounding away the volume of the observable universe divided by the average volume of a grain of sand? That is many more orders of magnitude than the amount of mass in the universe, which is a more usual comparison.
- Scarblac 1y ago
  Yes, that's only some normal number amount of orders of magnitude. Even 10,000,000^10,000,000 is already so large that it doesnt matter, let alone after exponentiating _the exponent_ nine times more.
  - wizzwizz4 1y ago
    It's the other way around: we're talking about 10^(10^(10^(10^…))) (which is vastly bigger).
- mckeed 1y ago
  With tetration you're not dealing with orders of magnitude anymore, but orders of magnitude of orders of magnitude.
- Chirono 1y ago
  Exactly. This number is so so much bigger than 10^100000 or however many grains of sand would fit, that dividing by that amount doesn’t really change it, certainly not enough to bring it down closer to 9,999,999sub10
- Straw 1y ago
  Yes, that's right, dividing by that ratio essentially barely affects the number in a sense that 'adjacent' numbers in that notation give a much bigger change. 10↑↑10,000,000 / (sand grains per universe) is vastly larger than, say, 10↑↑9,999,999 So on system we're using to write these numbers, there's really no better way to write (very big)/ (only universally big) than by writing exactly that, and then in the notation for very big, it pretty much rounds to just (very big).
- lupire 1y ago
  Here's a more common example of this sort of comparison: In significant figures, 1.0 billion minus 1.0 million equals 1.0 billion.
  - Nevermark 1y ago
    True but this is a ratio. However many universes in question, there is a qualitative difference between that many empty universes (with 1 grain), and that many completely packed with grain. Ask anybody who lives in one!
    - fwip 1y ago
      At very large numbers, even ratios don't really matter. For instance, if you personally owed $100 trillion, you wouldn't be much relieved by a court order that reduced your liability by 99%. Or, if you're looking at numbers in scientific notation, you don't much care about the difference between 2e40 and 5e40. In this case, the ratio is around 10^200. An incomprehensibly vast number, to be sure. But because tetration is the next operator up from exponentiation (the way exponents are from multiplication), any fixed divisor ceases to "matter" very quickly. The difference between 10^^10,000,000 and 10^^10,000,001 is (10^^10,000,000 to the tenth power), if my understanding is right. There's basically no way to get it into comprehensible territory even with repeated divisions. 10^^1 = 10, 10^^2 = 10^10 (ten billion), and 10^^3 is 10^(10^10) = 10^10,000,000. Already, dividing by 10^200 isn't going to meaningfully affect your number (10^99,999,800). 10^^10,000,000 is that kind of incomprehensible growth that we just saw from 1 to 2 to 3, repeated 10 million times.
      - Nevermark 1y ago
        > For instance, if you personally owed $100 trillion, you wouldn't be much relieved by a court order that reduced your liability by 99%. It is *never• true that differences don’t matter. Only true that in some respects the difference matters, others it does not. You manufactured a reasonable situation for differences not mattering. But if I had $1 trillion, 99% off $100 trillion would matter. As I noted, from the perspective of anyone in those universes, a 1 grain universe, or a solid grain universe would each be a spotty context to make a living. But in very different ways! So in this case, the ratio between two incomprehensibly large numbers, happens to be highly comprehensible under the circumstances in which they were described. I.e. universes and grains. One can imagine that one of unexplained constants of nature might be a result of differences between unimaginably large numbers. Which again shows, that there is no such things as numbers so large differences don’t matter. Only cases where they don’t matter, or do. As with all approximations.
fjfaase 1y ago
I wonder if the visible universe is large enough to write down the exact value of BB(6).
- Scarblac 1y ago
  It's not.
  - Alive-in-2025 1y ago
    I want some easier to comprehend number for BB(6), in decimal notation. But it's such a massive number I would need to invent a new notation to express that. I love this new (to me) concept of tetration number representation. 10-million sub 10, what is the number? Look at 3 sub 10 = which is (10^(10^10)). So that is 10 to the power of 10 billion. In regular decimal notation, that is a "1" with 10 billion "0"s following it. It takes 10 gigabytes of ram to represent the number in decimal notation, naively. The number of atoms in the universe is only 10^80, or 1,000...000 (80 zeroes). 10-million sub 10 is so huge, how much ram to represent it. This example is from https://www.statisticshowto.com/tetration-function-simple-definition-and-examples/ https://www.statisticshowto.com/tetration-function-simple-de...
- kaashif 1y ago
  It definitely isn't. The amount of information you can store in the universe is something like 10^120 bits. Even if I'm off by a trillion orders of magnitude it doesn't matter.
- aeve890 1y ago
  If you treat the observable universe as a closed system, you could try to apply the Bekenstein bound using - R ≈ 46.5 billion light-years (radius of the observable universe) - E ≈ total mass-energy content of the observable universe The mass-energy includes ordinary matter, dark matter, and dark energy. Current estimates suggest the observable universe contains roughly 10^53 kg of mass-energy equivalent. Plugging these into S ≤ 2πER/ℏc gives someting on the order of 10^120 bits of maximum information content. S ≤ 2πER/ℏc S ≤ (2 × 3.141593 × 3.036e+71 × 4.399e+26)/(1.055e-34 × 299792458) S ≤ 2.654135e+124 S ≤ 10^120 So, no.
Scarblac 1y ago
It boggles my mind that a number (an uncomputable number, granted) like BB(748) can be "independent of ZFC". It feels like a category error or something.
- eapriv 1y ago
  It’s not “an uncomputable number”.
- ChadNauseam 1y ago
  The number itself is not independent of ZFC. (Every integer can be expressed in ZFC.) What's independent of ZFC is the process of computing BB(748).
  - Straw 1y ago
    Sure, if someone just gives you the number, ZFC can represent it. But ZFC cannot prove that the value is correct, so how do you know you have the right number? Use a stronger proof system? Go a bit bigger and same issue.
    - ajkjk 1y ago
      Not an expert, but I've read about this a bit because it bothered me also and I think this is the answer: Most of these 'uncomputable' problems are uncomputable in the sense of the halting problem: you can write down an algorithm that should compute them, but it might never halt. That's the sense in which BB(x) is uncomputable: you won't know if you're done ever, because you can't distinguish a machine that never halts from one that just hasn't halted yet (since it has an infinite number of states, you can't just wait for a loop). So presumably the independence of a number from ZFC is like that also: you can't prove it's the value of BB(745) because you won't know if you've proved it; the only way to prove it is essentially to run those Turing machines until they stop and you'll never know if you're done. I'm guessing that for the very small Turing machines there is not enough structure possible to encode whatever infinitely complex states end up being impossible to deduce halting from, so they end up being Collatz-like and then you can go prove things about them using math. As you add states the possible iteration steps go wild and eventually do stuff that is beyond ZFC to analyze. So the finite value 745 isn't really where the infinity/uncomputability comes from-it comes from the infinite tape that can produce arbitrarily complex functions. (I wonder if over a certain number of states it becomes possible to encoding a larger Turing machine in the tape somehow, causing a sort of divergence to infinite complexity?)
deleted 1y ago
[deleted]
sedatk 1y ago
> 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. I thought it was a typo. First time I encounter tetration.
- griffzhowl 1y ago
  Continuing the theme of iteration: it was the first time I encountered pentation
  - tialaramex 1y ago
    One of the reasons I like the use of the number line in schools is that on the line it's more obvious when you're shown addition and multiplication and then later exponeniation that this is a pattern. With the number line, two natural questions arise and, hopefully by the time you're taught exponentiation the Math teacher knows enough math to confidently affirm the answer to both. Yes, it keeps going like this forever, that's called Hyperoperation. And yes, we did (probably) skip one, it's known as Successor-of and you were probably not explicitly shown this operator but it's the near end of that infinite succession. When arithmetic is introduced just as a way to, for example, count money, it's more directly practical in the moment, but you're not seeing the larger pattern.
    - Nevermark 1y ago
      Don't forget identity. Its range is small but important!
      - tialaramex 1y ago
        Fair!
- lbourdages 1y ago
  I've seen it before, but it was using Knuth's up-arrow notation [1], which I like because it generalizes easily. [1] https://en.wikipedia.org/wiki/Knuth's_up-arrow_notation https://en.wikipedia.org/wiki/Knuth's_up-arrow_notation
NooneAtAll3 1y ago
If you want to learn about actual Busy Beaver results, I suggest reading https://www.sligocki.com/ https://www.sligocki.com/ instead Unlike Aaronson, he actually is on the forefront of Busy Beaver research, and is one of the people behind the https://bbchallenge.org https://bbchallenge.org website
- moralestapia 1y ago
  >Unlike Aaronson, he actually is on the forefront of Busy Beaver research [...] Extremely bad ad hominem, I enjoyed Aaronson's read, nothing wrong with it.
  - lupire 1y ago
    That's not ad hominem at all.
  - refulgentis 1y ago
    Gently, seconding peer: that is not ad hominem :) Colloquially, I understand it's easy to think it means "saying something about someone that could be interpreted negatively" because that's the context it is read in it when it is used. The meaning is saying a logical argument is incorrect because of who wrote the argument.
    - charcircuit 1y ago
      But the comment is not just saying something negative. It is implying that claims from the article like "Then, three days ago, Tristan wrote again to say that mxdys has improved the bound again, to BB(6)>9_2_2_2" are not real results. The justification for these not being real results is solely based off whether author is actually on the forefront of research.
      - refulgentis 1y ago
        I think you're touching on something important here. OP isn't making a ad hominem fallacy in a logical argument sense - it's not saying "Aaronson is wrong because he's not a frontline researcher." But you're absolutely right to feel uncomfortable with their approach. There's something off-putting about dismissing someone's reporting of research developments, even if you prefer more comprehensive coverage, or there's more interesting things to say. The thing is, if that's ad hominem, so is any recommendation preferring one second-hand reporting over another -- ex. "if you want the actual news, read Tucker, not Krugman" isn't an ad hominem towards Krugman. Another example we see often on HN: saying "you should read the actual paper instead of this pop science" is a quite frequent, quite agreeable, and yet dull, contribution on say, a Quanta article. Yet, I imagine we agree this isn't an ad hominem. The real issue might be that OP conflates two different things: being a primary researcher versus being a good science communicator who accurately reports on others' work. Both roles have value, and questioning whether someone has filled one role doesn't necessarily invalidate their ability to fill the other. (this helped me understand my odd frustration with the dull comments on science articles: I emotionally engage with it as being mean / out of bounds, but its true, and in reality, what I'm frustrated with is there could always be a more detailed article, or even paper, but yet we all must publish)
charcircuit 1y ago
>imagine you had 10,000,000_10 grains of sand. Then you could … well, uh … you could fill about 10,000,000_10 copies of the observable universe with that sand. I hope that helps people visualize it! People can't visualize numbers that big. There's more ways to express numbers than just counting them. For example a single grain of sand has infinite states it can be in (there are an infinite amount of real numbers), so you could say a single grain of sand could represent BB(6). Combinations can grow exponentially, so that may be something useful to try and express it.
- Xcelerate 1y ago
  At some point big numbers become much more about the consistency strength of formal systems than “large quantities”. I.e., how well can a system fake being inconsistent before that fact it discovered? An inconsistent system faking consistency via BB(3) will be “found out” much quicker than a system faking consistency via BB(6). (What I mean by faking consistency is claiming that all programs that run longer than BB(n) steps for some n never halt.)
- unsnap_biceps 1y ago
  I'm confused about this example, isn't the count of grains of sand equal to the count of observable universes so it'd be a single grain of sand per universe?
  - heftig 1y ago
    The "about" does a lot of heavy lifting in this example. Dividing 10,000,000_10 by the number of grains that fit into one universe doesn't change it much. The 10,000,000 would get smaller somewhere in the deep depths of the decimal fraction.
- Dylan16807 1y ago
  If the universe rounds to the nearest Planck unit, then a grain of sand suddenly has not all that many states. Using infinite precision to make things seem tractable is sleight of hand in my book. Stick with integers when you're describing scale.
MichaelDickens 1y ago
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 <pentate> 5`.
- tromp 1y ago
  Thanks for sharing; your post would fit well as an answer to mine about Graham's number...
phs 1y ago
So what is the richest logic whose proofs can be enumerated with only a five state TM?
- tromp 1y ago
  That entirely depends on how you want to interpret a finite binary string as an enumeration of logic proofs?!
- LegionMammal978 1y ago
  While that question depends on what you count as an 'enumeration', there's the related question of "What's the richest logic that cannot prove the halting status of all 5-state TMs?" That is, what's the richest logic that some 5-state TM's halting status is independent of? I've pondered that version of the question a bit, but I couldn't get very far due to my lack of expertise in first-order logic. What I do know is that Skelet #17 [0] is one of the toughest machines to prove non-halting on a mathematical level [1], so any theory sufficient to prove that Skelet #17 doesn't halt is likely sufficient to decide the rest of the 5-state machines. [0] https://bbchallenge.org/1RB---_0LC1RE_0LD1LC_1RA1LB_0RB0RA https://bbchallenge.org/1RB---_0LC1RE_0LD1LC_1RA1LB_0RB0RA [1] https://arxiv.org/abs/2407.02426 https://arxiv.org/abs/2407.02426
tromp 1y ago
People on the bbchallenge Discord server are keen to speculate on how many Turing Machine states are needed to surpass Graham's Number, which is vastly larger than the 2^^2^^2^^9 achieved by the latest BB(6) champion. We know from the functional busy beaver [1] that Graham behaviour can come surprisingly early; a 49-bit lambda term suffices. There are only 77519927606 closed lambda terms of at most that size [2], compared to 4^12*23836540=399910780272640 unique 6-state Turing Machines [3]. With the achievement of pentation in only 6 states, several people now believe that 7 states should suffice to surpass Graham's. I would still find that rather surprising. A few days ago, I made a large bet with one of them on whether we would see proof of BB(7)>Graham's within the next 10 years. What do people here think? [1] https://oeis.org/A333479 https://oeis.org/A333479 [2] https://oeis.org/A114852 https://oeis.org/A114852 [3] https://oeis.org/A107668 https://oeis.org/A107668
- gpm 1y ago
  I can't pretend to be an expert, but I'll argue BB(7) is probably larger than Graham's number. BB has to grow faster than any computable sequence. What exactly that means concretely for BB(7) is... nothing other than handwaving... but it sort of means it needs to walk up the "operator strength" ladder very quickly... it eventually needs to grow faster than any computable operator we define (including, for example, up-arrow^n, and up-arrow^f(n) for any computable f). My gut feeling is that the growth between 47 million and 2^^2^^2^^9 is qualitatively larger than the growth between 2^^2^^2^^9 and graham's number in terms of how strong the operator we need is (with gramah's number being g_64 and g here being roughly one step "above" up_arrow^n). So probably we should have BB(7)>Graham's number.
  - pinkmuffinere 1y ago
    Apologies if this feels adversarial, but I think your informal proof has an error, and I think I can explain it! Your proof rests primarily on this assertion: > BB has to grow faster than any computable sequence. This is almost true! BB(n) has to grow faster than any computable sequence _defined by an n-state Turing machine_. That last part is really important. (Note that my restatement is probably incorrect too, it is just correct enough to point out the important flaw I saw in your statement). This means that up-arrow^f(n) _can_ be larger than BB(n) — up-arrow^f(n) is not restricted by a Turing machine at all. As an easy example, consider f(n) = BB(n)^2. You may still be right about BB(7) being bigger than Graham’s number, even if your proof is not bulletproof
d_silin 1y ago
Any time I see such results from computation complexity theory, I realize that any current zeitgeist of "super-intelligent AI are gods" is complete bullshit. You can convert every atom of observable Universe into a substrate for supercomputer, you can harness energies of supermassive black holes to power it, but running a humble BB(6) to halting state would be forever out of its reach.
- istjohn 1y ago
  That strawman never stood a chance.
ryandrake 1y ago
> For those tuning in from home, here BB(6) is the 6th 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. Oh! Of course! That sure clears things up for this non-expert. This is clearly a hardcore blog for people who have been doing this kind of research for decades. Kind of awesome to stumble upon something so unapologetically dense and jargony and written for a very specific audience!
- clbrmbr 1y ago
  The definition there is standard undergraduate computer science theory. Maybe not standard for software engineering though.
- Bjartr 1y ago
  That should be enough for someone with an undergrad CS education to at least get a sense of what's going on if they haven't encountered the busy beaver problem before. Is it niche jargon, absolutely, but to say it's only accessible to people who have put in decades is selling yourself short.
  - ryandrake 1y ago
    Hmm, interesting. It’s been 30 years since my engineering degree (not CS) and I’d have to look up what a Turing machine is. I think I remember one professor briefly mentioned it as “This is something the CS majors care deeply about but nobody else in the industry does.” Where I was, the CS degree was essentially a math degree dressed up in a hoodie.
    - Bjartr 1y ago
      > This is something the CS majors care deeply about but nobody else in the industry does Correct, the industry cares a lot more about Software Engineering than Computer Science. > CS degree was essentially a math degree dressed up in a hoodie. To a first approximation, that's what it's supposed to be. CS is a field of mathematics. It's not a trade school course.
vismit2000 1y ago
Scott Aaronson | How Much Math Is Knowable? [Harward CMSA]: https://www.youtube.com/watch?v=VplMHWSZf5c https://www.youtube.com/watch?v=VplMHWSZf5c Recently on HN (couple of months ago): https://news.ycombinator.com/item?id=43776477 https://news.ycombinator.com/item?id=43776477

272 points by bdr 1y ago

> So I said, imagine you had 10,000,000sub10 grains of sand. Then you could … well, uh … you could fill about 10,000,000sub10 copies of the observable universe with that sand. I don't get this part. Is it really rounding away the volume of the observable universe divided by the average volume of a grain of sand? That is many more orders of magnitude than the amount of mass in the universe, which is a more usual comparison.

Scarblac 1y ago
Yes, that's only some normal number amount of orders of magnitude. Even 10,000,000^10,000,000 is already so large that it doesnt matter, let alone after exponentiating _the exponent_ nine times more.
- wizzwizz4 1y ago
  It's the other way around: we're talking about 10^(10^(10^(10^…))) (which is vastly bigger).
mckeed 1y ago
With tetration you're not dealing with orders of magnitude anymore, but orders of magnitude of orders of magnitude.
Chirono 1y ago
Exactly. This number is so so much bigger than 10^100000 or however many grains of sand would fit, that dividing by that amount doesn’t really change it, certainly not enough to bring it down closer to 9,999,999sub10
Straw 1y ago
Yes, that's right, dividing by that ratio essentially barely affects the number in a sense that 'adjacent' numbers in that notation give a much bigger change. 10↑↑10,000,000 / (sand grains per universe) is vastly larger than, say, 10↑↑9,999,999 So on system we're using to write these numbers, there's really no better way to write (very big)/ (only universally big) than by writing exactly that, and then in the notation for very big, it pretty much rounds to just (very big).
lupire 1y ago
Here's a more common example of this sort of comparison: In significant figures, 1.0 billion minus 1.0 million equals 1.0 billion.
- Nevermark 1y ago
  True but this is a ratio. However many universes in question, there is a qualitative difference between that many empty universes (with 1 grain), and that many completely packed with grain. Ask anybody who lives in one!
  - fwip 1y ago
    At very large numbers, even ratios don't really matter. For instance, if you personally owed $100 trillion, you wouldn't be much relieved by a court order that reduced your liability by 99%. Or, if you're looking at numbers in scientific notation, you don't much care about the difference between 2e40 and 5e40. In this case, the ratio is around 10^200. An incomprehensibly vast number, to be sure. But because tetration is the next operator up from exponentiation (the way exponents are from multiplication), any fixed divisor ceases to "matter" very quickly. The difference between 10^^10,000,000 and 10^^10,000,001 is (10^^10,000,000 to the tenth power), if my understanding is right. There's basically no way to get it into comprehensible territory even with repeated divisions. 10^^1 = 10, 10^^2 = 10^10 (ten billion), and 10^^3 is 10^(10^10) = 10^10,000,000. Already, dividing by 10^200 isn't going to meaningfully affect your number (10^99,999,800). 10^^10,000,000 is that kind of incomprehensible growth that we just saw from 1 to 2 to 3, repeated 10 million times.
    - Nevermark 1y ago
      > For instance, if you personally owed $100 trillion, you wouldn't be much relieved by a court order that reduced your liability by 99%. It is *never• true that differences don’t matter. Only true that in some respects the difference matters, others it does not. You manufactured a reasonable situation for differences not mattering. But if I had $1 trillion, 99% off $100 trillion would matter. As I noted, from the perspective of anyone in those universes, a 1 grain universe, or a solid grain universe would each be a spotty context to make a living. But in very different ways! So in this case, the ratio between two incomprehensibly large numbers, happens to be highly comprehensible under the circumstances in which they were described. I.e. universes and grains. One can imagine that one of unexplained constants of nature might be a result of differences between unimaginably large numbers. Which again shows, that there is no such things as numbers so large differences don’t matter. Only cases where they don’t matter, or do. As with all approximations.

fjfaase 1y ago

I wonder if the visible universe is large enough to write down the exact value of BB(6).

Scarblac 1y ago
It's not.
- Alive-in-2025 1y ago
  I want some easier to comprehend number for BB(6), in decimal notation. But it's such a massive number I would need to invent a new notation to express that. I love this new (to me) concept of tetration number representation. 10-million sub 10, what is the number? Look at 3 sub 10 = which is (10^(10^10)). So that is 10 to the power of 10 billion. In regular decimal notation, that is a "1" with 10 billion "0"s following it. It takes 10 gigabytes of ram to represent the number in decimal notation, naively. The number of atoms in the universe is only 10^80, or 1,000...000 (80 zeroes). 10-million sub 10 is so huge, how much ram to represent it. This example is from https://www.statisticshowto.com/tetration-function-simple-definition-and-examples/ https://www.statisticshowto.com/tetration-function-simple-de...
kaashif 1y ago
It definitely isn't. The amount of information you can store in the universe is something like 10^120 bits. Even if I'm off by a trillion orders of magnitude it doesn't matter.
aeve890 1y ago
If you treat the observable universe as a closed system, you could try to apply the Bekenstein bound using - R ≈ 46.5 billion light-years (radius of the observable universe) - E ≈ total mass-energy content of the observable universe The mass-energy includes ordinary matter, dark matter, and dark energy. Current estimates suggest the observable universe contains roughly 10^53 kg of mass-energy equivalent. Plugging these into S ≤ 2πER/ℏc gives someting on the order of 10^120 bits of maximum information content. S ≤ 2πER/ℏc S ≤ (2 × 3.141593 × 3.036e+71 × 4.399e+26)/(1.055e-34 × 299792458) S ≤ 2.654135e+124 S ≤ 10^120 So, no.

Scarblac 1y ago

It boggles my mind that a number (an uncomputable number, granted) like BB(748) can be "independent of ZFC". It feels like a category error or something.

eapriv 1y ago
It’s not “an uncomputable number”.
ChadNauseam 1y ago
The number itself is not independent of ZFC. (Every integer can be expressed in ZFC.) What's independent of ZFC is the process of computing BB(748).
- Straw 1y ago
  Sure, if someone just gives you the number, ZFC can represent it. But ZFC cannot prove that the value is correct, so how do you know you have the right number? Use a stronger proof system? Go a bit bigger and same issue.
  - ajkjk 1y ago
    Not an expert, but I've read about this a bit because it bothered me also and I think this is the answer: Most of these 'uncomputable' problems are uncomputable in the sense of the halting problem: you can write down an algorithm that should compute them, but it might never halt. That's the sense in which BB(x) is uncomputable: you won't know if you're done ever, because you can't distinguish a machine that never halts from one that just hasn't halted yet (since it has an infinite number of states, you can't just wait for a loop). So presumably the independence of a number from ZFC is like that also: you can't prove it's the value of BB(745) because you won't know if you've proved it; the only way to prove it is essentially to run those Turing machines until they stop and you'll never know if you're done. I'm guessing that for the very small Turing machines there is not enough structure possible to encode whatever infinitely complex states end up being impossible to deduce halting from, so they end up being Collatz-like and then you can go prove things about them using math. As you add states the possible iteration steps go wild and eventually do stuff that is beyond ZFC to analyze. So the finite value 745 isn't really where the infinity/uncomputability comes from-it comes from the infinite tape that can produce arbitrarily complex functions. (I wonder if over a certain number of states it becomes possible to encoding a larger Turing machine in the tape somehow, causing a sort of divergence to infinite complexity?)

deleted 1y ago

[deleted]

sedatk 1y ago

> 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. I thought it was a typo. First time I encounter tetration.

griffzhowl 1y ago
Continuing the theme of iteration: it was the first time I encountered pentation
- tialaramex 1y ago
  One of the reasons I like the use of the number line in schools is that on the line it's more obvious when you're shown addition and multiplication and then later exponeniation that this is a pattern. With the number line, two natural questions arise and, hopefully by the time you're taught exponentiation the Math teacher knows enough math to confidently affirm the answer to both. Yes, it keeps going like this forever, that's called Hyperoperation. And yes, we did (probably) skip one, it's known as Successor-of and you were probably not explicitly shown this operator but it's the near end of that infinite succession. When arithmetic is introduced just as a way to, for example, count money, it's more directly practical in the moment, but you're not seeing the larger pattern.
  - Nevermark 1y ago
    Don't forget identity. Its range is small but important!
    - tialaramex 1y ago
      Fair!
lbourdages 1y ago
I've seen it before, but it was using Knuth's up-arrow notation [1], which I like because it generalizes easily. [1] https://en.wikipedia.org/wiki/Knuth's_up-arrow_notation https://en.wikipedia.org/wiki/Knuth's_up-arrow_notation

NooneAtAll3 1y ago

If you want to learn about actual Busy Beaver results, I suggest reading https://www.sligocki.com/ https://www.sligocki.com/ instead Unlike Aaronson, he actually is on the forefront of Busy Beaver research, and is one of the people behind the https://bbchallenge.org https://bbchallenge.org website

moralestapia 1y ago
>Unlike Aaronson, he actually is on the forefront of Busy Beaver research [...] Extremely bad ad hominem, I enjoyed Aaronson's read, nothing wrong with it.
- lupire 1y ago
  That's not ad hominem at all.
- refulgentis 1y ago
  Gently, seconding peer: that is not ad hominem :) Colloquially, I understand it's easy to think it means "saying something about someone that could be interpreted negatively" because that's the context it is read in it when it is used. The meaning is saying a logical argument is incorrect because of who wrote the argument.
  - charcircuit 1y ago
    But the comment is not just saying something negative. It is implying that claims from the article like "Then, three days ago, Tristan wrote again to say that mxdys has improved the bound again, to BB(6)>9_2_2_2" are not real results. The justification for these not being real results is solely based off whether author is actually on the forefront of research.
    - refulgentis 1y ago
      I think you're touching on something important here. OP isn't making a ad hominem fallacy in a logical argument sense - it's not saying "Aaronson is wrong because he's not a frontline researcher." But you're absolutely right to feel uncomfortable with their approach. There's something off-putting about dismissing someone's reporting of research developments, even if you prefer more comprehensive coverage, or there's more interesting things to say. The thing is, if that's ad hominem, so is any recommendation preferring one second-hand reporting over another -- ex. "if you want the actual news, read Tucker, not Krugman" isn't an ad hominem towards Krugman. Another example we see often on HN: saying "you should read the actual paper instead of this pop science" is a quite frequent, quite agreeable, and yet dull, contribution on say, a Quanta article. Yet, I imagine we agree this isn't an ad hominem. The real issue might be that OP conflates two different things: being a primary researcher versus being a good science communicator who accurately reports on others' work. Both roles have value, and questioning whether someone has filled one role doesn't necessarily invalidate their ability to fill the other. (this helped me understand my odd frustration with the dull comments on science articles: I emotionally engage with it as being mean / out of bounds, but its true, and in reality, what I'm frustrated with is there could always be a more detailed article, or even paper, but yet we all must publish)

charcircuit 1y ago

>imagine you had 10,000,000_10 grains of sand. Then you could … well, uh … you could fill about 10,000,000_10 copies of the observable universe with that sand. I hope that helps people visualize it! People can't visualize numbers that big. There's more ways to express numbers than just counting them. For example a single grain of sand has infinite states it can be in (there are an infinite amount of real numbers), so you could say a single grain of sand could represent BB(6). Combinations can grow exponentially, so that may be something useful to try and express it.

Xcelerate 1y ago
At some point big numbers become much more about the consistency strength of formal systems than “large quantities”. I.e., how well can a system fake being inconsistent before that fact it discovered? An inconsistent system faking consistency via BB(3) will be “found out” much quicker than a system faking consistency via BB(6). (What I mean by faking consistency is claiming that all programs that run longer than BB(n) steps for some n never halt.)
unsnap_biceps 1y ago
I'm confused about this example, isn't the count of grains of sand equal to the count of observable universes so it'd be a single grain of sand per universe?
- heftig 1y ago
  The "about" does a lot of heavy lifting in this example. Dividing 10,000,000_10 by the number of grains that fit into one universe doesn't change it much. The 10,000,000 would get smaller somewhere in the deep depths of the decimal fraction.
Dylan16807 1y ago
If the universe rounds to the nearest Planck unit, then a grain of sand suddenly has not all that many states. Using infinite precision to make things seem tractable is sleight of hand in my book. Stick with integers when you're describing scale.

MichaelDickens 1y ago

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 <pentate> 5`.

tromp 1y ago
Thanks for sharing; your post would fit well as an answer to mine about Graham's number...

phs 1y ago

So what is the richest logic whose proofs can be enumerated with only a five state TM?

tromp 1y ago
That entirely depends on how you want to interpret a finite binary string as an enumeration of logic proofs?!
LegionMammal978 1y ago
While that question depends on what you count as an 'enumeration', there's the related question of "What's the richest logic that cannot prove the halting status of all 5-state TMs?" That is, what's the richest logic that some 5-state TM's halting status is independent of? I've pondered that version of the question a bit, but I couldn't get very far due to my lack of expertise in first-order logic. What I do know is that Skelet #17 [0] is one of the toughest machines to prove non-halting on a mathematical level [1], so any theory sufficient to prove that Skelet #17 doesn't halt is likely sufficient to decide the rest of the 5-state machines. [0] https://bbchallenge.org/1RB---_0LC1RE_0LD1LC_1RA1LB_0RB0RA https://bbchallenge.org/1RB---_0LC1RE_0LD1LC_1RA1LB_0RB0RA [1] https://arxiv.org/abs/2407.02426 https://arxiv.org/abs/2407.02426

tromp 1y ago

People on the bbchallenge Discord server are keen to speculate on how many Turing Machine states are needed to surpass Graham's Number, which is vastly larger than the 2^^2^^2^^9 achieved by the latest BB(6) champion. We know from the functional busy beaver [1] that Graham behaviour can come surprisingly early; a 49-bit lambda term suffices. There are only 77519927606 closed lambda terms of at most that size [2], compared to 4^12*23836540=399910780272640 unique 6-state Turing Machines [3]. With the achievement of pentation in only 6 states, several people now believe that 7 states should suffice to surpass Graham's. I would still find that rather surprising. A few days ago, I made a large bet with one of them on whether we would see proof of BB(7)>Graham's within the next 10 years. What do people here think? [1] https://oeis.org/A333479 https://oeis.org/A333479 [2] https://oeis.org/A114852 https://oeis.org/A114852 [3] https://oeis.org/A107668 https://oeis.org/A107668

gpm 1y ago
I can't pretend to be an expert, but I'll argue BB(7) is probably larger than Graham's number. BB has to grow faster than any computable sequence. What exactly that means concretely for BB(7) is... nothing other than handwaving... but it sort of means it needs to walk up the "operator strength" ladder very quickly... it eventually needs to grow faster than any computable operator we define (including, for example, up-arrow^n, and up-arrow^f(n) for any computable f). My gut feeling is that the growth between 47 million and 2^^2^^2^^9 is qualitatively larger than the growth between 2^^2^^2^^9 and graham's number in terms of how strong the operator we need is (with gramah's number being g_64 and g here being roughly one step "above" up_arrow^n). So probably we should have BB(7)>Graham's number.
- pinkmuffinere 1y ago
  Apologies if this feels adversarial, but I think your informal proof has an error, and I think I can explain it! Your proof rests primarily on this assertion: > BB has to grow faster than any computable sequence. This is almost true! BB(n) has to grow faster than any computable sequence _defined by an n-state Turing machine_. That last part is really important. (Note that my restatement is probably incorrect too, it is just correct enough to point out the important flaw I saw in your statement). This means that up-arrow^f(n) _can_ be larger than BB(n) — up-arrow^f(n) is not restricted by a Turing machine at all. As an easy example, consider f(n) = BB(n)^2. You may still be right about BB(7) being bigger than Graham’s number, even if your proof is not bulletproof

d_silin 1y ago

Any time I see such results from computation complexity theory, I realize that any current zeitgeist of "super-intelligent AI are gods" is complete bullshit. You can convert every atom of observable Universe into a substrate for supercomputer, you can harness energies of supermassive black holes to power it, but running a humble BB(6) to halting state would be forever out of its reach.

istjohn 1y ago
That strawman never stood a chance.

ryandrake 1y ago

> For those tuning in from home, here BB(6) is the 6th 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. Oh! Of course! That sure clears things up for this non-expert. This is clearly a hardcore blog for people who have been doing this kind of research for decades. Kind of awesome to stumble upon something so unapologetically dense and jargony and written for a very specific audience!

clbrmbr 1y ago
The definition there is standard undergraduate computer science theory. Maybe not standard for software engineering though.
Bjartr 1y ago
That should be enough for someone with an undergrad CS education to at least get a sense of what's going on if they haven't encountered the busy beaver problem before. Is it niche jargon, absolutely, but to say it's only accessible to people who have put in decades is selling yourself short.
- ryandrake 1y ago
  Hmm, interesting. It’s been 30 years since my engineering degree (not CS) and I’d have to look up what a Turing machine is. I think I remember one professor briefly mentioned it as “This is something the CS majors care deeply about but nobody else in the industry does.” Where I was, the CS degree was essentially a math degree dressed up in a hoodie.
  - Bjartr 1y ago
    > This is something the CS majors care deeply about but nobody else in the industry does Correct, the industry cares a lot more about Software Engineering than Computer Science. > CS degree was essentially a math degree dressed up in a hoodie. To a first approximation, that's what it's supposed to be. CS is a field of mathematics. It's not a trade school course.

vismit2000 1y ago

Scott Aaronson | How Much Math Is Knowable? [Harward CMSA]: https://www.youtube.com/watch?v=VplMHWSZf5c https://www.youtube.com/watch?v=VplMHWSZf5c Recently on HN (couple of months ago): https://news.ycombinator.com/item?id=43776477 https://news.ycombinator.com/item?id=43776477