Hacker News Reader

Hacker News

Comment by jl6 | Hacker News Reader

Full thread

jl6

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_%...

View on HN

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.

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

[1] https://bbchallenge.org/~pascal.michel/ha

Thanks for this information, it's very helpful! Also I had no idea that "googological strength" was a thing. :-)

I'll just leave this here: https://googology.fandom.com/wiki/Googology_Wiki

> 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.

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".

Or the next big things were implementable at n-3, but finally pay off at n+1?

What does "practically" mean here?

Busy Beaver champion programs are said to run for super-exponentially many steps. But nobody has actually run their simulators for that many steps. Instead, simulators can prove tape fast-forwarding rules. Basically, you look for repeating tape patterns. If you can prove the pattern is correct, then you can apply that transformation again if some tape circumstance shows up again.

For example (using run-length encoding), 1^n 0 1^m might become 1^(n-1) 0 1^(m+2)

When the rule is applied, the transformation is applied directly to the tape, generally by manipulating some count variables.

Now, how many machine steps does it take to apply this transformation? Well, TBH I'm not really sure. It seems kinda complicated, especially when the rules get more elaborate. If you are trying to run your simulator as fast as possible, you probably don't want to bother calculating it at all anyway, since you can always rerun the analysis at a more leisurely pace later.

So when I say that marks are "more practically important", I mean that marks are central to the operation of advanced simulators, whereas steps are a derived afterthought value.

Logically, the steps are more important, since they give you an easy method for solving the halting problem for the state/color class.

So far, the markiest programs are also the steppiest. My conjecture is that they will turn out to be different in infinitely many classes. If they were always the same, you would be able to get the logical primacy of steps just from working with marks. And that sounds too good to be true.

Pascal Michael's website hasn't been updated with the last results yet, right?

Under "Turing machines with 5 states and 2 symbols", there's no mention of the definitive results

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

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.

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/

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.

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.

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-spag...

I think human's attempts to make busy beavers may be clean, but chaos being hard to control doesn't matter to the "real" busy beavers because we pick from the entire range. I think that's one of the hardest things to wrap human brains around trying to intuit how the sequence behaves. We are selecting for the maximally pathological machines. If there is a frontier between chaos, order, and simply never halting, we are deliberately hunting the one that is just barely on that line. I don't think clean patterns can ever hope to compete with one that is exploiting chaos to just that bit that barely walks up to the line and doesn't quite, after a number of steps beyond any human ability to write down with any amount of notation we have, cross it.

But yeah, it's an opinion. :)

> We are selecting for the maximally pathological machines.

This is not quite right. We're selecting for maximally long-running (or mark-producing, etc) programs. Whether those programs turn out to be "pathological" in some sense is an open question, and a question that can only be answered (to a limited extent) by observing and analyzing actual champion machines. Apriori, there's nothing we can say about what a champion program will do or what its code will be like. The Spaghetti Code Conjecture says that these champion programs will tend to be complicated. I have argued in the past that this may not be the case. It's entirely possible that the code of a champion program will be written more or less straightforwardly, and its long-running-ness comes from executing some bizarre and exotic mathematical function.

Actually, I think the more likely outcome is that some champions will be spaghetti and some will be clean. If they were all spaghetti or all clean, then that fact could be exploited to speed up the search process by discarding all programs not matching the property. And that sounds too good to be true, so it probably isn't. Maybe BB(8) champion is clean, BB(9) is spaghetti, etc, and there are no reliable trends.

"Actually, I think the more likely outcome is that some champions will be spaghetti and some will be clean."

Ah, now, that's thinking with pathologies.

Clean code isn't the same as clean behavior/output, though. A Collarz calculator would have rather unclean output.

Fractals or fractal-like things seem to be the main way you get "interesting" behaviour out of very simple rules. Procedurally generated art/content tends to use them a lot (look at e.g. demoscene programs).

Reply on news.ycombinator.com