Hacker News Reader

Comment by shawnz | Hacker News Reader

You might already know this, but the busy beaver function grows faster than any computable function. So although the best known lower bound of BB(6) can be expressed with just pentation, generally speaking the BB function is certainly beyond any standard operation in terms of fast growth

View on HN

Tree(n) is considered computable.

BB(n) surpasses Tree(n) by - at most - when n=2645.

And likely shortly after BB(100).

Now consider the following definition for an exponentially faster growing number:

HyperTree(n) is where the Tree function is nested x times, where x is the result of tree(n).

HyperTree(3) = Tree(Tree(Tree..{Tree(3) long}...Tree(3))))...)

BB(X) would (should) still outpace HyperTree(x) at some value of x.

I don't know where to begin even to give an upper or lower bound of when BB(x) is larger than HyperTree(x).

It's been shown to be surpassed at n=150, which as you note is likely very generous. Hypertree would typically only require a few more states. Hypertree doesn't grow meaningfully faster than Tree. Hypertree(3) is what would be called a Salad number, combining a very fast growing function with some very weak one(s) such as iteration, which in the Fast Growing Hierarchy corresponds to taking the successor if an ordinal.

The growth of BB is certainly mind-boggling; however, I personally find its growth rate so untouchable as obviate any attempt at understanding. There's nothing to gain purchase on.

The fast growing hierarchy, on the other hand, provides oodles of structure for us to explore, and we can construct numbers that are vastly larger than anything BB(6) is likely to hit. In fact, this is why we use the fast growing hierarchy to approximate really big numbers all the time!

When we take something like f_Γ_0 and try to unpack even just the barest surface of its size, I get a feeling of vastness similar to those videos of diving endlessly into fractals.

Reply on news.ycombinator.com