Hacker News Reader

Comment by pdonis | Hacker News Reader

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.

View on HN

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

Reply on news.ycombinator.com