Comment by xelxebar
5 hours ago
Busy Beaver gets a lot of love, but the fast growing hierarchy is both constructive and can go way, way, waaaaay beyond current known BB bounds. This makes their size much more viscerally apparent than gesturing vaguely at BB(BB(BB(100))) or whatever, IMHO.
David Metzler has this really cool playlist "Ridiculously Huge Numbers" that digs into the details in an accessible way:
https://www.youtube.com/playlist?list=PL3A50BB9C34AB36B3
By the end, you're thinking about functions that grow so fast TREE is utterly insignificant. Surprisingly, getting there just needs a small bit of machinery beyond Peano Arithmetic [0].
Then you can ponder doing all that but making a tiny tweak by replacing succesorship with BB. Holy cow...
[0]:https://en.wikipedia.org/wiki/Theories_of_iterated_inductive...
> the fast growing hierarchy is both constructive
Only the part for which we have well-defined fundamental sequences is constructive. As far as I know, there is no such system of FS defined up to PTO(Z_2), the Proof Theoretic Ordinal of second order arithmetic, while growth rate at that ordinal can be programmed in under 42 bytes.
> waaaaay beyond current known BB bounds
I have to disagree here. The Proof Theoretic Ordinal of ZFC + infinitely many inaccessibles can be reach with a program of only a few thousand bits, and that is already extremely high up into the FGH.