4 ms·

BB(0) = 0 BB(1) = 1 BB(2) = 4 BB(3) = 6 BB(4) = 13 They just proved that BB(5) = 47,176,870. It is known that BB(6) must be at least 10^10^...^10 (a tower

by jl6 2y ago

BB(0) = 0 BB(1) = 1 BB(2) = 4 BB(3) = 6 BB(4) = 13 They just proved that BB(5) = 47,176,870. It is known that BB(6) must be at least 10^10^...^10 (a tower of exponents fifteen levels high). https://en.wikipedia.org/wiki/Busy_beaver#Known_values_for_%CE%A3_and_S https://en.wikipedia.org/wiki/Busy_beaver#Known_values_for_%...

deleted 2y ago
[deleted]
deleted 2y ago
[deleted]
pdonis 2y ago
The definitions of the "BB" function don't all appear to be the same. The article referenced in this overall discussion says BB(2) = 6. In the notation of the Wikipedia article you reference, this would be S(2) = 6; S is the number of steps. What has now been proved is that S(5) = 47,176,870. However, your BB values for 0, 1, 2, 3, and 4 match the Wikipedia article's notation for Sigma; Sigma is the number of 1s written on the tape at halting. In that notation, what has now been proved is Sigma(5) = 4098.
- LegionMammal978 2y ago
  Yeah, this is a bit confusing, and the subject of repeated internal controversy. Most of the twentieth-century authors focused on the number of 1s, Σ(n), following Radó's original practice of treating σ(M) as the score of a machine M in the "Busy Beaver game". But when Aaronson re-popularized it in 2020 [0], he used BB(n) to denote the number of steps (which Radó called S(n)), and the bbchallenge project has been using this latter convention for publicity. Pascal Michel's website [1] has all the Σ(n) and S(n) bounds up to n = 7. Personally, I think both functions have their strengths and weaknesses. Σ(n) is easier to calculate for machines that run too long to be simulated directly (e.g., Skelet #1 from the article) but leave a known pattern on the tape, and it also has historical priority. But S(n) has a simpler argument for being undecidable, since it provides a trivial filter for testing if a candidate machine cannot halt. Also, σ(M) is a bit weird in that it has no lower bound in terms of s(M), since an adversarial machine could do a colossal amount of work before wiping its tape at the end. Regardless, past BB(3), there isn't any known size where the champion machines for Σ(n) and S(n) are different. (At least, the sets of champion machines aren't disjoint: Σ(5) = 4098 is shared by both the S(5) champion and another machine that runs a quarter as long.) The score of a machine is dominated by googological strength rather than technicalities in the definition. [0] https://scottaaronson.blog/?p=4916 https://scottaaronson.blog/?p=4916 [1] https://bbchallenge.org/~pascal.michel/ha https://bbchallenge.org/~pascal.michel/ha
  - pdonis 2y ago
    Thanks for this information, it's very helpful! Also I had no idea that "googological strength" was a thing. :-)
    - Sharlin 2y ago
      I'll just leave this here: https://googology.fandom.com/wiki/Googology_Wiki https://googology.fandom.com/wiki/Googology_Wiki
  - nickdrozd 2y ago
    > past BB(3), there isn't any known size where the champion machines for Σ(n) and S(n) are different. My feeling is that this trend cannot continue forever, and for infinitely many N they are different. If they are always the same, then you could find the steps champion just by finding the marks champion. This would be convenient, because as you pointed out, steps are more logically important, while marks are more practically important. But this feels too good to be true, and so it probably isn't.
    - LegionMammal978 2y ago
      Hmm, around n = 2 or k = 2, there are only 2 added transitions for a machine to do "the next big thing" googologically, so that doesn't leave much slack for many different machines at the same level. But maybe that could happen closer to the n = k line, where each increment adds many new transitions. Or to the contrary, maybe each increment just does several "next big things".
      - cwillu 2y ago
        Or the next big things were implementable at n-3, but finally pay off at n+1?
    - lupire 2y ago
      What does "practically" mean here?
Natsu 2y ago
Looking at the pictures on Wikipedia regarding those programs, it's interesting how they seem to result in fractals.
- LegionMammal978 2y ago
  This mainly has to do with the BB(5) champion having "bouncing" behavior: it moves from the left side of the current pattern to the right side and back again, each time extending it slightly. Since the time it takes to grow the pattern is strictly proportional to its current size, you end up with a bunch of parabolas that appear self-similar.
- jerf 2y ago
  That is because these are small. Small machines can not help but still have those sorts of patterns in them. See all the simple 1-D automata of interest, for instance: https://atlas.wolfram.com/01/01/ https://atlas.wolfram.com/01/01/ As you step up I am fairly confident you'll see the winners get noisier and noisier. They'll have some sort of pattern, just ones you won't be able to comprehend. For some suitable definition of "noisier" this might even be a provable claim.
  - Natsu 2y ago
    Wouldn't it make more sense for the longest running ones to be fractal in a sense given that the self-similarity is sort of compressible? I guess we'll probably never know, because it's not clear that we'll ever find another BB winner.
  - 317070 2y ago
    Ha, the funny thing is, there are conjectures both ways! Some people think winners get noisier and noisier, the spaghetti code conjecture. Others actually think the winners get cleaner and cleaner, the clean code conjecture. Personally, I am slightly leaning towards clean code being more powerful. Chaos is hard to control. https://nickdrozd.github.io/2022/03/12/formal-theory-of-spaghetti-code.html https://nickdrozd.github.io/2022/03/12/formal-theory-of-spag...

by jl6 2y ago

deleted 2y ago

[deleted]

deleted 2y ago

[deleted]

pdonis 2y ago

The definitions of the "BB" function don't all appear to be the same. The article referenced in this overall discussion says BB(2) = 6. In the notation of the Wikipedia article you reference, this would be S(2) = 6; S is the number of steps. What has now been proved is that S(5) = 47,176,870. However, your BB values for 0, 1, 2, 3, and 4 match the Wikipedia article's notation for Sigma; Sigma is the number of 1s written on the tape at halting. In that notation, what has now been proved is Sigma(5) = 4098.

LegionMammal978 2y ago
Yeah, this is a bit confusing, and the subject of repeated internal controversy. Most of the twentieth-century authors focused on the number of 1s, Σ(n), following Radó's original practice of treating σ(M) as the score of a machine M in the "Busy Beaver game". But when Aaronson re-popularized it in 2020 [0], he used BB(n) to denote the number of steps (which Radó called S(n)), and the bbchallenge project has been using this latter convention for publicity. Pascal Michel's website [1] has all the Σ(n) and S(n) bounds up to n = 7. Personally, I think both functions have their strengths and weaknesses. Σ(n) is easier to calculate for machines that run too long to be simulated directly (e.g., Skelet #1 from the article) but leave a known pattern on the tape, and it also has historical priority. But S(n) has a simpler argument for being undecidable, since it provides a trivial filter for testing if a candidate machine cannot halt. Also, σ(M) is a bit weird in that it has no lower bound in terms of s(M), since an adversarial machine could do a colossal amount of work before wiping its tape at the end. Regardless, past BB(3), there isn't any known size where the champion machines for Σ(n) and S(n) are different. (At least, the sets of champion machines aren't disjoint: Σ(5) = 4098 is shared by both the S(5) champion and another machine that runs a quarter as long.) The score of a machine is dominated by googological strength rather than technicalities in the definition. [0] https://scottaaronson.blog/?p=4916 https://scottaaronson.blog/?p=4916 [1] https://bbchallenge.org/~pascal.michel/ha https://bbchallenge.org/~pascal.michel/ha
- pdonis 2y ago
  Thanks for this information, it's very helpful! Also I had no idea that "googological strength" was a thing. :-)
  - Sharlin 2y ago
    I'll just leave this here: https://googology.fandom.com/wiki/Googology_Wiki https://googology.fandom.com/wiki/Googology_Wiki
- nickdrozd 2y ago
  > past BB(3), there isn't any known size where the champion machines for Σ(n) and S(n) are different. My feeling is that this trend cannot continue forever, and for infinitely many N they are different. If they are always the same, then you could find the steps champion just by finding the marks champion. This would be convenient, because as you pointed out, steps are more logically important, while marks are more practically important. But this feels too good to be true, and so it probably isn't.
  - LegionMammal978 2y ago
    Hmm, around n = 2 or k = 2, there are only 2 added transitions for a machine to do "the next big thing" googologically, so that doesn't leave much slack for many different machines at the same level. But maybe that could happen closer to the n = k line, where each increment adds many new transitions. Or to the contrary, maybe each increment just does several "next big things".
    - cwillu 2y ago
      Or the next big things were implementable at n-3, but finally pay off at n+1?
  - lupire 2y ago
    What does "practically" mean here?

Natsu 2y ago

Looking at the pictures on Wikipedia regarding those programs, it's interesting how they seem to result in fractals.

LegionMammal978 2y ago
This mainly has to do with the BB(5) champion having "bouncing" behavior: it moves from the left side of the current pattern to the right side and back again, each time extending it slightly. Since the time it takes to grow the pattern is strictly proportional to its current size, you end up with a bunch of parabolas that appear self-similar.
jerf 2y ago
That is because these are small. Small machines can not help but still have those sorts of patterns in them. See all the simple 1-D automata of interest, for instance: https://atlas.wolfram.com/01/01/ https://atlas.wolfram.com/01/01/ As you step up I am fairly confident you'll see the winners get noisier and noisier. They'll have some sort of pattern, just ones you won't be able to comprehend. For some suitable definition of "noisier" this might even be a provable claim.
- Natsu 2y ago
  Wouldn't it make more sense for the longest running ones to be fractal in a sense given that the self-similarity is sort of compressible? I guess we'll probably never know, because it's not clear that we'll ever find another BB winner.
- 317070 2y ago
  Ha, the funny thing is, there are conjectures both ways! Some people think winners get noisier and noisier, the spaghetti code conjecture. Others actually think the winners get cleaner and cleaner, the clean code conjecture. Personally, I am slightly leaning towards clean code being more powerful. Chaos is hard to control. https://nickdrozd.github.io/2022/03/12/formal-theory-of-spaghetti-code.html https://nickdrozd.github.io/2022/03/12/formal-theory-of-spag...