# Tetration Forum

You're currently viewing a stripped down version of our content. View the full version with proper formatting.
(I migrated here 'cos the other eretrandre forum is too quiet )

Recently, in the course of trying to find extremely fast-growing computable functions, I stumbled upon a curious connection between Cantor's transfinite ordinals and functions on the natural numbers.

I won't repeat the definition of an ordinal number here, it's easily found on Wikipedia or other online sources. Cantor really only developed ordinal arithmetic up to exponentiation: he got as far as the limit of the sequence $\omega, \omega^{\omega}, \omega^{\omega^{\omega}}, \ldots$, calling it epsilon_0. This ordinal satisfies the fixed point property x=w^x. After that, he defined other epsilon numbers as subsequent ordinals with the same property.

In the course of researching higher-order operations such as tetration on the natural numbers, I noticed that epsilon_0 is the ideal candidate for w tetrated to w. Once you accept this, it's not too hard to imagine w[4](w+1), w[4](w+2), .... (I shall use the notation x[4]y to denote x tetrated to y, for the obvious reason that we want to also consider higher-order operations later.) This is very obvious---at least intuitively. However, it's not so simple to define rigorously, as I discovered recently when trying to formalize what I'm dealing with. The main problem is that exponentiation is non-associative, and because of this, one cannot easily define what is meant by w[4]x for x greater than w. (I'm leaving out the details 'cos it's not very interesting.)

So I proceeded along this line of reasoning: we intuitively understand w[4](w+1) to be a tower of exponents containing a stretch of w instances of w, followed by another w in the w'th position. We can lay out each element of the tower in a sequence: w, w, w, ... (w times), w. If we add another w to the base of the tower, we see that this sequence doesn't change. So what that means is that w^(w[4](w+1)) = w[4](w+1). In other words, it must be an epsilon number.

If we then start with w[4]w=epsilon_0, and construct larger ordinals from it, we see that epsilon_0+1, epsilon_0+2, ... all do not satisfy the fixed point property x=w^x. Multiplying epsilon_0 by 2, 3, 4, ... w, etc., all don't satisfy this property either. Neither does epsilon_0^2, epsilon_0^3, ... epsilon_0^w, .... In fact, one quickly realizes that any ordinal between w[4]w and w[4](w+1) does not satisfy this property. Therefore, we must conclude that w[4](w+1) = epsilon_1.

A similar line of reasoning shows that w[4](w+x) = epsilon_x. In other words, even though we don't know how to define ordinal tetration using transfinite recursion on lower-order operations, we can define it in terms of the epsilon numbers.

Now, we move on. Consider the ordinal w[4](w[4]w), which I shall denote as w[4]w[4]w (from now on, we'll assume right-to-left associativity, just to reduce the number of parentheses we need to write). By our definition of tetration, this ordinal is epsilon_epsilon_0. Similarly, w[4]w[4]w[4]w = epsilon_epsilon_epsilon_0. In other words, w[5](n+1) = epsilon_epsilon_...epsilon_0, where there are n epsilon's.

This defines pentation on ordinals up to w[5]w, which is the smallest ordinal satisfying x=epsilon_x. To define pentation for bigger right arguments, we need to go beyond the epsilon numbers.

Fortunately, a system for producing larger ordinals already exists: the Veblen hierarchy. It is defined in terms of a class of functions phi_y:

For y=0, phi_y(x) = w^x (base case)
For y=z+1, phi_y(x) = the x'th fixed point of phi_z
For limit ordinals y, phi_{y}(x) = union of all fixed points of phi_z, where z is less than y

Note that for our construction to be valid, x must be either an ordinal smaller than w or an ordinal we have already constructed with previous applications of the phi function.

So phi_0(0) = w^0 = 1, phi_0(1)=w, phi_0(2)=w^2, etc.. Now that we've constructed w^n for finite n, we can pass these ordinals to phi_0: phi_0(w)=w^w, phi_0(w^w)=w^w^w, and so forth. The limit (fixed point) of phi_0 is phi_0(phi_0(phi_0(...)))=w^w^w^...=epsilon_0. This is, by definition, phi_1(0).

Then again, by definition, phi_1(1) is the next fixed point of phi_0: that is, the next ordinal satisfying x=w^x. In other words, phi_1(1)=epsilon_1=w[4](w+1). So phi_1 is just the epsilon numbers.

Now we come to the interesting part: phi_2(0) is defined to be the first fixed point of phi_1, or, in other words, the fixed point of the epsilon numbers, epsilon_epsilon_epsilon_... = w[4]w[4]w[4]... = w[5]w. So we see that phi_2(0)=w[5]w. What is phi_2(1)? It is the next fixed point of the epsilon function: i.e., the next ordinal satisfying w[4]x = x. Using a parallel argument as we used above to determine that w[4](w+1)=epsilon_1, we can see that phi_2(1) must equal w[5](w+1). In other words, we can now define pentation: w[5]x = phi_2(x).

With this definition, we see that phi_2(phi_2(w)) = w[5]w[5]x, phi_2(phi_2(phi_2(w))) = w[5]w[5]w[5]w, and so forth. The fixed point of phi_2, then, must be w[5]w[5]w[5]... = w[6]w. By the definition of phi, it must be the case that w[6]w = phi_3(0).

The pattern is now clear: w[n]w = phi_{n-3}(0), and w[n](w+x) = phi_{n-3}(x). This gives us a rigorous definition of tetration, pentation, hexation, ... for the ordinals.

The next interesting ordinal is phi_w(0): this is the limit of all the nth order operations. So, it must be the ordinal equivalent of the Ackermann function!

But we have only barely begun. If we let A^i(x) to be the i'th iterate of the Ackermann function (i.e., A^2(x) = A(A(x)), A^3(x) = A(A(A(x))), ...). Then A^w(w) = phi_{w+1}(0). Call this function B. Now let B^i(x) be the i'th iterate of B. Then B^w(w) = phi_{w+2}(0). Call this function C. Then C^w(w) = phi_{w+3}(0). And so on, until we reach the w'th step of creating more iterates. That function then corresponds with phi_{w+w}(0).

As you can see, it's not so much that the ordinals themselves are all that interesting; it is the fact that they let us create larger and larger computable functions on the natural numbers.

As it stands, we've hardly begun to scratch the surface of the Veblen hierarchy. Keep in mind that phi_0(2)=w^2, so we have hardly begun to reach phi_{phi_0(2)}(0) = phi_{w^2}(0). Once we reach that, then we can go further to get to phi_{phi_0(3)}(0), phi_{phi_0(4)}(0), ... and so on, and eventually to phi_{phi_0(w)}(0)=phi_{phi_{phi_0(0)}(0)}(0). At each new subscript to phi, the number of steps required to reach the next level increase INSANELY fast. After the first few subscripts of phi_y, the Ackermann function already looks like a microscopic wimp compared to the functions being generated by the phi function.

We can keep going, until we get to phi_phi_phi_... = Gamma_0. This ordinal is known as the Feferman-Schütte ordinal, and is so insanely large that phi_Gamma_0(0) = Gamma_0. It is also so insanely large that performing fixed point operations on it (as the phi function does) does not get you significantly past it. This ordinal has quite an important role in logic and proof theory, but that's not my interest here. My interest here is in that fact that this ordinal should correspond with some function F on the natural numbers. Since Gamma_0 is still countable, and moreoever, still recursive, this means that F must be computable!!!! Yet F is so unimaginably fast-growing that it dwarfs all currently-known large number functions (excepting non-computable ones like the Busy Beaver function), including most attempts at making these functions grow faster. The only function I know of that can go significantly beyond F is the busy beaver function, which is non-computable. As far as computable functions go, F is pretty close to the limit of computability!

We may also derive from Gamma_0 an operation on the natural numbers. As such an operation, it far, far, far, FAR transcends ANY operation that anyone has ever considered before. If you ever need to name the largest computable natural number you can think of, this operation will come in handy.

Anyway, there are still open questions to consider:

- Although we have found elegant constructions for higher-order operations (tetration, pentation, ...) on ordinals where the left argument is w, we haven't really defined these operations for other left arguments. For finite numbers, it's easy to define, but it may not be that easy for transfinite arguments. We could attempt to define x[4]y, for example, as the smallest ordinal z satisfying z=x^z, but I'm not sure if x[4](y+n) always coincides with the n'th ordinal satisfying this relation. More investigation is necessary to prove this.

- It's not at all clear how to compute that super-fast function F derived from the ordinal Gamma_0. We do know that it's computable, and we do know, at least in theory, that recursing up the Veblen hierarchy will give us a way to compute it. However, a lot of details are missing, among the most important of which is, how to computationally jump from the n'th level of a phi subscript to the next subscript. I've actually explored functions much, much farther past the Ackermann function and its iterates as described above, and I still haven't gotten to phi_phi_1(0) yet. We do know that F must be computable, but how to actually compute it seems intractible at the moment.

- It's possible to move even higher past the Veblen hierarchy: Gamma_0 is merely the first fixed point of the phi function. We can move up to Gamma_1, Gamma_2, ... or even Gamma_Gamma_Gamma_.... I believe these huge ordinals must still be computable, because they are still below the so-called Church-Kleene ordinal $\omega_1^{\mbox{CK}}$, which is the union of all recursive ordinals. Note that even this ordinal is still countable!! (The first uncountable ordinal $\omega_1$ is simply far beyond comprehension.) However, I'm not sure if it's even possible to fathom how to compute functions/operations correspond with the higher Gamma ordinals. If anybody has any ideas, I'd be interested.
Hmm, apparently, I'm not the first one to discover the correlation between higher-order arithmetic operations and the recursive transfinite ordinals:

According to this page, the Feferman-Schütte ordinal $\Gamma_0$ is the supremum of all ordinals (finitely) describable using recursive operations. Yet it is still recursive (and therefore computable), so I wonder if there may be a way to reach it. Obviously, some other method than merely building on previous operations will be needed.
Amazing ... !

I mean: W = omega-omegated-omega. Still ... computable?.

GFR
You do realize that that's just the Ackermann function applied to omega, right? w[w]w = A(w,w), which corresponds with phi_2(0). That's definitely computable, although not primitive recursive. (Primitive recursive functions correspond with the operations of finite order.)

But, as I've said above, the Ackermann function is but a mere scratch at the top 0.01% of the tip of the iceberg. As it stands, I've only barely made it 1% of the way down from the top of the tip of the iceberg---I still have no idea how to computationally get to phi_phi_1(0). And that's but one puny step out of infinitely-many needed to reach the Feferman-Schütte ordinal. (And this is disregarding the fact that every subsequent step is immensely larger than all previous steps combined.)
"M'illumino ... d'Immenso." I enlighten me of ... Immensity".
(Ungaretti)

GFR
Dear All,

After further research into the correspondence between (countable) ordinals and functions, I believe I have discovered the function that represents a growth rate corresponding to the Feferman-Schütte ordinal $\Gamma_0$. The details are here:

http://eusebeia.dyndns.org/veblen/etf.html

Interestingly enough, the function turns out to be related to transforming binary trees. In particular, the diagonalized function E(n) involves transforming a left-branching linear chain to a right-branching linear chain, and in the process adding many nodes... MANY nodes (so many that I suspect it's not possible to describe using any other known notation for large numbers). All this is done by a very simple-looking two-step transform, applied repeatedly until the tree becomes a right-branching chain.

Anyway, let me know what y'all think.

P.S. Oh, and I should add that even though I derived the function based on the structure of transfinite ordinals, the function itself has no direct connection with ordinals. It's really just a binary tree transforming function. (Just so the anti-Cantorians here don't write it off as uninteresting. )
quickfur Wrote:http://eusebeia.dyndns.org/veblen/etf.html

...

Anyway, let me know what y'all think.

Just skimmed through your article and asking myself how this function can be expressed with a recursive definition ...
bo198214 Wrote:[...]
Just skimmed through your article and asking myself how this function can be expressed with a recursive definition ...
I've not thought about that... but I assume it must be possible since the algorithm obviously can be expressed as a Turing machine, so it must be recursive. I'm not sure how exactly to go about deriving a recursive definition for it, though.

Maybe one way is to perform a depth-first traversal on the tree, left child first, and recursively linearize the left-most children. So, in computer pseudocode, it could be something like this:

Code:
linearize(T,m) {     if (is_rightbranching_chain(T.left_subtree) and         is_rightbranching_chain(T.right_subtree))     {         ... (perform the transformation... not sure how to express this recursively yet)     } else {         T.left_subtree = linearize(T.left_subtree, m);         T.right_subtree = linearize(T.right_subtree, m);         return T;     } }

Once we work out the pseudocode, maybe there's a way to factor it into a recursive function...?
Just a quick update on this subject... the ETF function I defined deals only with binary trees. This corresponds with the Veblen hierarchy, which is generated by the binary Veblen function phi_a(b). Oswald Veblen himself actually went further than this, to define ordinal functions of n variables. These correspond with functions on n-ary trees; it is possible to define an n-ary tree transformation function along similar lines as I have, that reduces a left-branching tree to a very, very long right-branching one.

Now if we take the limit of this process (since there is no end to the ordinals), we have a function that deals trees with omega children. (Some care has to be taken here, to ensure that repeated applications of the function will terminate: this can be assured by substituting a finite, but varying, value for omega---in effect, we're dealing with trees where the number of children is indexed.) This brings us up to something called the "small Veblen ordinal".

But Veblen went further: now that we've reached omega, the next logical step is to create a function with omega+1 arguments (or equivalently, a tree with omega+1 children per node). Then omega+2, omega+3, ... and so forth. Eventually, we may just define a function that takes an ordinal number of arguments. Once we get to this point, we might as well take the output of our functions, which is an ordinal, and use that as the number of arguments to our next-higher function, and so forth.

Somewhere along the line, we get to the point where the ordinals generated are so large, that to get any farther, we will need a function with X number of arguments, where X is an ordinal larger than any we have generated so far. The smallest such X is called the "large Veblen ordinal", and represents the limit of what is attainable using ordinal functions---or, equivalently, it represents the limit of computable functions that can be reached by iteration and diagonalization. In other words, it is iteration and diagonalization taken to the logical conclusion.

(As a side note, Jonathan Bowers' Exploding Array Function has the potential to span the ordinals below X. A very impressive feat for someone with not much formal training!)

Iteration and diagonalization will never reach X, so the function that corresponds with X represents the fastest-growing function that can be constructed from the successor function via iteration and diagonalization.

The kicker is that X lies below the Church-Kleene ordinal. So not only is it computable, it barely scratches the surface of fast-growing computable functions! To get beyond X, we will truly need unconstrained recursion, of the kind that even iteration and diagonalization will not suffice. I've no idea what such functions might look like: but they are all still computable!

So here lies the frontier of pushing the upper limits of fast-growing computable functions.

(Personally I think simply leaping to uncomputable functions is a cop-out... many people who will quickly name BBN in the arms-race of fast-growing functions have absolutely no idea how unimaginably huge it is... only by exploring what lies before it, can we truly appreciate how incredibly fast growing it is!) </soapbox>
(02/21/2008, 08:16 PM)quickfur Wrote: [ -> ]A similar line of reasoning shows that w[4](w+x) = epsilon_x. In other words, even though we don't know how to define ordinal tetration using transfinite recursion on lower-order operations, we can define it in terms of the epsilon numbers.
Omega tetrated to the (omega plus one) equals omega to the power of omega tetrated to the omega. Omega tetrated to the omega equals epsilon zero. So Omega tetrated to the (omega plus one) equals omega to the power of epsilon zero. Omega to the power of epsilon zero equals epsilon zero. So Omega tetrated to the (omega plus one) equals epsilon zero.
Omega tetrated to the (omega plus one) being anything other than epsilon zero, such as epsilon one would not follow the recursive rule of tetration; that a tetated to the (b plus one) equals a to the power of a tetrated to the b.
Quote:Since Gamma_0 is still countable, and moreoever, still recursive, this means that F must be computable!!!! Yet F is so unimaginably fast-growing that it dwarfs all currently-known large number functions (excepting non-computable ones like the Busy Beaver function), including most attempts at making these functions grow faster. The only function I know of that can go significantly beyond F is the busy beaver function, which is non-computable. As far as computable functions go, F is pretty close to the limit of computability!
Nope! F is not even close to the limit of computability! There are far faster growing computable functions! Such as Loader's function.
Quote:We may also derive from Gamma_0 an operation on the natural numbers. As such an operation, it far, far, far, FAR transcends ANY operation that anyone has ever considered before.

Faster growing functions had been considered before then. Loader's function was programed in two thousand one.