Comment by dmichulke

11 years ago

Given the other comments I wonder whether the Meta-Algorithm for big numbers is basically:

Compose a state space that expands as quickly as possible in terms of the argument(s) and define some property of the state space as the result.

Looking at it this way, I'd say:

"Hyper-exponentiation" (Ackermann, tetration and so on) is basically counting the number of states in a well-defined state space.

BB(X) is equivalent to generating automatically the state space (via a search over all possible state spaces that can be constructed with a TM with X states) and returning the size of the maximum.

This means that BB(X) is smaller than the sum of the sizes of all possible state spaces constructible via that TM.

But BB(X+1) is aware of that trick (summing state space sizes) and uses it already (or more probably something better), so it doesn't really matter and you might as well just increase X by one to include all the tricks you had in mind for BB(X).

Anyone thoughts on that?

2 comments

dmichulke

Reply
cousin_it  11 years ago

BB_2(X) uses a different trick. It asks for the largest number computable by any program of length X that's allowed to call a BB oracle with arbitrary arguments. That's more powerful than any finite expression involving BB and computable functions, like BB(F(X)), BB(F(BB(X))), etc.

More generally, I expect there to not be any "meta-algorithm" for naming big numbers. Every big step will require a new insight. A similar problem is inventing notations for large ordinals: http://en.wikipedia.org/wiki/Ordinal_notation