Who can name the bigger number? (Math Stuff)?

Question

I read some thing a while ago on "Who can name the bigger number". It basically said that it was whoever had the deeper paradigm. The progression is Exponentials, the Ackermann Sequence, Busy Beaver Numbers/Turing Numbers, and then the infinitely repeating Busy Beaver Sequence (By Rado). I was wondering if a deeper paradigm has been found?

Answer 1

Well some obvious extensions -- one can define for instance, S(S(n)), and then S(S(S(n))), and so on (where S(n) is the maximum number of steps taken by an n-state Turing machine before halting). Or for a deeper paradigm, you can consider oracle machines -- Turing machines that additionally have a nonphysical device called an oracle which accepts an input and computes the result in a single step. Note that since we aren't assuming the oracle is a physical device, we may have it output the answer even to uncomputable functions, such as the busy beaver function. Now, we can define a busy beaver function for the new oracle machines, which will grow much faster than the busy beaver function for regular Turing machines (for instance, we can easily construct a machine that has fewer than n states that writes n, calls the oracle, and then runs for at least S(n) states based on the output of the oracle). Of course, one immediately realizes that as powerful as they are (such an oracle machine could trivially solve the halting problem, compute Chaitin's constant and the Kolmogorov complexity of an arbitrary string), it would not be able to solve every problem -- in particular, it would be unable to solve its own halting problem or compute the busy beaver function for oracle machines. Which immediately suggests the idea of a super-oracle machine with an oracle for the busy beaver function for the first oracle machine. The busy beaver function of that machine would grow even faster. Of course, this machine would not be unlimited either, so we might imagine a machine with an oracle for the busy beaver function for the super-oracle machine, whose busy beaver function grows even faster. And we could continue this process indefinitely, producing the whole arithmetic hierarchy. And then (bringing infinity into the game of finding very large finite numbers), we could imagine an ω-oracle machine, whose oracle provides the busy beaver functions for _all_ the n-oracle machines produced by iterating the above procedure any finite number of times, thus transcending that hierarchy (the machine itself would still have finite inputs and outputs -- it would call its oracle with an ordered pair of numbers, one specifying the level of the oracle of the machine whose busy beaver function it wants and the second specifying the maximum number of states). And that machine would in turn have its own busy beaver function, so we could imagine a machine with an oracle for that... Needless to say, we could go through all the countable ordinal numbers in this way. Now, I do think we can stop at countable infinities, because although you might be able to define the oracle function for a ω₁-oracle machine, It would be difficult to actually access that function (to have the oracle output a specific number, you would have to specify both the maximum number of states and also the level of the oracle of the machine you wanted. But for ω₁, there would be uncountably many different oracle levels below it, and only countably many ways of specifying that level, so the oracle machine would be unable to access the full power of its oracle).

Is there a deeper paradigm? Probably. But even if you don't know what it is, fear not -- you may always resort to the simple tactic of replying to (unimaginably huge number) with (unimaginably huge number) + 1.

Answer 2

If you count infinity as a number (which you should).

There are then several different infinities! (must work out how to get maths expressions on this keyboard!).

Using examples, not the maths.

If I is infinity, I0 is where you map the number of points on a straight line.

I1 is mapping the points on a straight line to a 2D surface.

I2 is mapping the points on a 2D surface to a 3D object.

Etc. Last I heard I4 was the highest accepted as having any real world meaning, but in n dimensions the largest infinity is In.