OK, have to make technical corrections here. Busy Beaver is not a complexity class, complexity classes do not grow. Busy Beaver function grows faster than any computable function, but I doubt it’s the “fastest” at anything, seeing as you can always just take e^BB(n), e.g.
Ugh, thank you. I seem to have gotten complexity classes and algorithmic complexity mixed up. Busy Beaver’s algorithmic complexity grows asymptotically faster than any computable function, so far as considerations like Big-O notation are concerned. In those sorts of cases, I think that even for functions like e^BB(n), the BB(n) part dominates. Or so Wikipedia tells me.
ETA: cousin_it has pointed out that there uncomputable functions which dominate Busy Beaver.
As Eliezer pointed out on HN, there is a way to define numbers that dominate BB values as decisively as BB dominates the Ackermann function, but you actually need some math knowledge to make the next step, not just stack BB(BB(...)) or something. (To be more precise, once you make the step, you can beat any person who’s “creatively” using BB’s and oracles but doesn’t know how to make the same step.) And after that quantum leap, you can make another quantum leap that requires you to understand another non-trivial bit of math, but after that leap he doesn’t know what to do next, and I, being a poor shmuck, don’t know either. If you want to work out for yourself what the steps are, don’t click the link.
OK, have to make technical corrections here. Busy Beaver is not a complexity class, complexity classes do not grow. Busy Beaver function grows faster than any computable function, but I doubt it’s the “fastest” at anything, seeing as you can always just take e^BB(n), e.g.
Ugh, thank you. I seem to have gotten complexity classes and algorithmic complexity mixed up. Busy Beaver’s algorithmic complexity grows asymptotically faster than any computable function, so far as considerations like Big-O notation are concerned. In those sorts of cases, I think that even for functions like e^BB(n), the BB(n) part dominates. Or so Wikipedia tells me.
ETA: cousin_it has pointed out that there uncomputable functions which dominate Busy Beaver.
Sure, but my point is it’s not the “fastest” of anything unless you want to start defining some very broad equivalences...
As Eliezer pointed out on HN, there is a way to define numbers that dominate BB values as decisively as BB dominates the Ackermann function, but you actually need some math knowledge to make the next step, not just stack BB(BB(...)) or something. (To be more precise, once you make the step, you can beat any person who’s “creatively” using BB’s and oracles but doesn’t know how to make the same step.) And after that quantum leap, you can make another quantum leap that requires you to understand another non-trivial bit of math, but after that leap he doesn’t know what to do next, and I, being a poor shmuck, don’t know either. If you want to work out for yourself what the steps are, don’t click the link.