Thursday, June 5, 2008

1977 is over & so is G

One googologist's rant against the indeflatable popularity of Graham's Number
( written by Sbiis Saibian )


Graham's Number or simply G has replaced the googolplex as "largest number ever" in the popular imagination. Ronald Graham actually invented Graham's Number back in 1977 as an upper bound to a problem in graph theory. Although the Guinness Book of World records has made the number famous, among professional mathematicians it's more of a joke. For one, the upper bound is absurdly large, and the actual value is probably a GREAT deal smaller, and secondly the proof has proven to be flawed at best.

While G may be recognized by the Guinness Book, and is certainly the largest number taken seriously, it is NOT by a long shot the "Biggest Number ever defined!". The number was created over 30 years ago, and yet it is treated like it's current and cutting edge. Hardly! It's already lost that title within professional circles as even larger numbers have been used in "serious mathematical proofs" since then. Furthermore, the requirement that a candidate largest number be somehow connected to serious mathematics is of little concern to the amateur mathematician who likes to come up with large numbers just for the sake of it. Accordingly, the largest numbers defined by humans are usually the product of an untamed imagination, having little to do with serious mathematics, even when the untamed imagination happens to be that of a professional mathematician.

G is popular because it is well known, it takes a little while to explain, any intelligent person can understand it, and it builds on the familiar operator sequence of addition, multiplication, exponentiation, tetration, etc. But if we want to talk about the largest number humans have yet defined than we've got a LONG way to go from Graham's !

First off, you need to completely shift your perspective on this. Yes from a practical standpoint G is absolutely absurdly and unimaginably huge ! But consider this, assuming someone only knew how to add, and how to interpret recursive formulas, Graham's Number can be defined as follows ...

{a,b,1} = a^b
{a,1,c} = a
{a,b,c}= {a,{a,b-1,c},c-1}
G(1) = {3,3,4}
G(n) = {3,3,G(n-1)}
G = G(64)

It only requires 6 lines to define it. Graham's is simply an elementary recursive function applied to the operation level in the operator hierarchy. " What ?! simply that ?! That doesn't sound simple at all", you might be thinking. However everything about G is already well understood, and elementary recursion and hierarchies like this can be applied a ridiculous number of times, where G on the other hand simple contains ONE OF EACH !

By this point your probably thinking this is BS, or that I'm talking about trivial stuff like G+1 , G^2 , G^G, G^^G, G(65) , G(100) , G(googolplex) ,G(3^^^^3) , G(Graham's Number) ,
G(G(G(G(...(G))..)) with G G's, etc.

nope, all of that is "trivial" (as mathematicians love to say). It's the 21st century, and all of this is just elementary recursive stuff.

There are MANY new numbers on the block that should get more attention, but are overshadowed by G, not because G is larger, but because it came from professional circles! Some of these numbers are so large, and difficult to describe, that they make G look more elementary than adding two and two! All of these amazing numbers were invented by a little known amateur mathematician by the name of Jonathan Bowers. In 2002 he published his first website where he discussed for the first time his "Super giant Numbers".

To describe his numbers Bowers invented a special notation called "array notation". With it one can easily express numbers much larger than anything which can be expressed using Knuth Up-arrows, Steinhaus Polygons, the G function, and even Conway Chain arrows!

How does it work? Well Bowers first creates a function which can have any number of entries, just like chain arrows, but unlike them they do NOT work on the last two entries, but rather the first two. The effect of this shift is profound and gives Bowers arrays an advantage over alternative notations. We can use the curly braces to contain entries and commas to separate them. When the function is provided with no "entries", it takes on the default value of 1:

{ } = 1

When a single entry is present, the value of the array is the value of the entry:

{a} = a

2 entries are equivalent to raising the first entry to the power of the second (in his old notation the first two entries would be added together) ...

{a,b} = a^b

3 entries is equivalent to Knuth's up arrows ...

{a,b,c} = a^^^^....^^^b with c up arrows

After this we need to know something about the rules Bowers uses for what he calls "linear arrays". These are the simplest kind of arrays he works with. In linear arrays we can have ANY number of entries, provided they are only separated by commas. If the linear array contains 4 or more entries we need to follow a set of special rules ...

1. If the last entry is a 1 then remove it ... {a,b,...,k,1} = {a,b,...,k}
2. If the 2nd entry is 1, return 1st entry ... {a,1,c,...,k} = a
3. If entries 3 ~ k-1 = 1 & the kth entry does NOT equal 1 ...

{a,b,1,1,...,1,1,k,...,z} = {a,a,a,a,...,a,{a,b-1,1,1,...,1,1,k,...,z}, k-1 , ... z }

4. If rules 1~3 do NOT apply then ...

{a,b,c,...,k}= {a,{a,b-1,c,...,k}, c-1 , .... , k }

Now let's compare Bowers arrays to the Graham's function.

Firstly ...

G(1) = {3,3,4} = 3^^^^3
G(2) = {3,3,{3,3,4}}
G(3) = {3,3,{3,3,{3,3,4}}}
etc.

Although arrays may not seem very impressive at the moment, you have to consider this. Bowers has set up his arrays so that every new type of array explodes the old type of array. 4 entries far surpasses 3.

for example take the seemingly harmless example ...

{3,3,1,2}

Using the rules to evaluate we find this ...

{3,3,1,2} = {3,3,{3,2,1,2},1} = {3,3,{3,3,{3,1,1,2},1},1} =

{3,3,{3,3,3,1},1} = {3,3,{3,3,3},1} = {3,3,{3,3,3}} = 3^^^...^^^3 with 3^^^3 up arrows.

Look familiar ? That's right! It's the same growth exhibited by Graham's function. Note that...

{3,2,1,2} = 3^^^3 < 3^^^^3 = G(1)

Furthermore...

{3,3,1,2} = 3^^^...^^^3 w/3^^^3 ^s > 3^^^^3 = G(1)

with a little bit of inductive reasoning we can conclude that ...

{3,65,1,2} < G(64) < {3,66,1,2}

and in general that:

{3,n+1,1,2} < G(n) < {3,n+2,1,2}

But we've only just begun with Bower's system. What happens if the third entry is a 2? Let's again take a seemingly harmless example:

{3,3,2,2}

Applying the rules we find that:

{3,3,2,2} = {3,{3,2,2,2},1,2} =
{3,{3,{3,1,2,2},1,2},1,2} = {3,{3,3,1,2},1,2}

The 2nd entry in the outer array is ITSELF an array of {3,3,1,2} which is already greater than G(1) or 3^^^^3.

so Now we can say ...

{3,{3,3,1,2},1,2} > {3,G(1),1,2} > G(G(1) - 2 ) = G(3^^^^3 - 2 )

which is roughly G(G(1))

That's right! We are recursively plugging in Graham's function into itself ! But this is only the effect of having a 2 as the 3rd and 4th entry ...

{3,3,2,2} > G(G(1))

{3,4,2,2} > G(G(G(1)))

{3,5,2,2} > G(G(G(G(1))))

But this is just the beginning. You see the 2 in the 4th entry is producing 2nd order operations. Think of it like this... Imagine the Graham's function is 2nd order addition. Then Plugging G into itself ( meaning GGG...GG ) is 2nd order multiplication. Now imagine 2nd order exponents , tetration, pentation, and so on.

Now you should realize the pattern. We can create a hierarchy of 2nd order operators which are exploded ( just like Graham's function explodes the standard operator hierarchy ) by the 3rd order addition.

Now we can have nth order hierarchies. This is the power of ONLY 4 entries !!!

Bowers 4 entry arrays already are powerful enough to keep up with chain arrows of arbitrary length.

People who know about Chain arrows often scoff at Graham's Number since it's between 3-->64-->1-->2 and 3-->65-->1-->2.

Consider however that 3-->3-->3-->3 ( a number that Conway invented using his notation ) is much larger than G, yet is still smaller than Bowers {3,3,3,3}

Bowers calls {3,3,3,3} , tetratri , for obvious reasons. Tetratri uses 3rd order exponents, and is much larger than G.

Is tetratri the largest number ? Nope.

Bowers is well aware that even this number surpasses anything else out there in the same vein, but he doesn't stop here, but continues into the unknown.

5 entry arrays go way beyond chain arrows. To imagine this think of a chain like ...

3-->3-->3-->....-->3-->3 with " 3 --> 3 --> 3 --> 3 " threes in the chain

This number is still smaller than {3,3,1,1,2} .

The 5th entry produces orders of 4 entry arrays in the same way that the 4th entry produces orders of operator hierarchies . YIKES ! It hurts to think about it too much.

And example would be {10,10,10,10,10} a number Bowers calls pentadecal .

Now Bowers linear arrays are extremely powerful, and Bowers is prepared to use them to the fullest. He defines even larger numbers such as ...

Iteral = {10,10,10,10,10,10,10,10,10,10} ( That's 10 tens )

Iteralplex = {10,10,10,10,10, ... ... ... ... ... ... , 10,10,10} with Iteral 10's !

Now we have just blasted off into new territory.

What Bowers does next is even more incredible. Bowers creates "array structures" . He was the first person to discover that if you attempt to extend "entry based algorithms" the most efficient and logical approach is to create a structural hierarchy.

Linear arrays are a hierarchy of entries. Every entry is superseded by the entry to it's immediate right.

Bowers realized that he could surpass linears and create planar arrays, or 2-D arrays.

Actually the dimensionality is superfluous. We can still write such arrays in a linear fashion, as long as we create a new kind of "comma". Bowers uses " (1) " to separate "linear blocks" to form "planar blocks". To show you what I mean, and also show you just how Powerful Bowers notation is look at this:

First he creates a new rule ...

{b,p (1) 2} = {b,b,b,...,b,b} with p b's

The "b , p " is the first linear block , and " 2 " is the 2nd linear block . Together they can form linear arrays of arbitrary length. Now observe how easy this makes it to express iteral and iteralplex ...

Iteral = {10,10 (1) 2 }
Iteralplex = {10,3,2 (1) 2} = {10,{10,10(1)2} (1) 2 } = {10,iteral (1) 2}

Notice the similarity of the rules used to expand iteralplex. That's right. We can use linear arrays to expand linear arrays, thus the 2 at the end represents 2nd order linear arrays. We can then have 3rd order , 4th , ... nth order . But it just keeps going . The 2nd linear block can become 2 entries. For example Bowers has coined the number ...

Hyperal = { 10,10 (1) 10,10 }

Note that the hyperal is like a 2x2 grid of 10's ( if we imagine it as a 2 dimensional display )

Bowers continues his system. He has a number called xappol which is a 10 x 10 grid of 10's , and a xappolplex which is a xappol x xappol grid of 10's.

Where could Bowers possibly go from here ?! 3-dimensional arrays, 4-dimensions , heck , arbitrary numbers of dimensions.

Here's a REALLY awesome number Bowers coined ...

Imagine a 100-dimensional cube where each dimension has a length of 10. Now imagine every entry is a 10. When this array is solved it produces the insane number gongulus ( G's seem to be a popular letter for large numbers )

Let's stop for a moment. Consider the googolplex and how it is totally humbled by Graham's Number. Now think about it , gongulus totally mops the floor with Graham's Number. G is only about the size of a 4 entry array with a 2 in the last entry, but a gongulus requires 10^100 entries ( That's a googol entries. Even the number of entries is huge ! ) arrayed in a complex 100-dimensional structure ! In fact, even this comparison doesn't do the gongulus justice, because by the time the 100-dimensional array is solved as a linear array the number of entries would exceed a Graham's Number, G(3^^^^3), G(G(...G(G)...)) w/G Gs, or anything else you could imagine using Graham's function, chain arrows, or even linear arrays, planar arrays, realmic arrays, flunic arrays, ... it's just INSANE! There is absolutely no comparison! Graham's Number was just the very beginning of large numbers all along! These are numbers for the 21st century ! Who would have thought that such a thing was possible.

At this point you may consider this too abstract. Actually dimensional arrays use a well defined algorithm. It also uses fairly simple notation. To separate n-dimensional blocks you use the
" ( n ) " separator.

For example, Bowers has a 3-d array called dimentri. It is a 3x3x3 array of 3's. We can even write it out in full ...

{3,3,3(1)3,3,3(1)3,3,3(2)3,3,3(1)3,3,3(1)3,3,3(2)3,3,3(1)3,3,3(1)3,3,3}

The commas separate entries inside linear blocks, the (1) separate linear blocks inside planar blocks, and the (2) separate planes inside "realms".( Bowers uses a lot of whimsical terminology. For example he refers to 4-d blocks as flunes )

Bowers actually has the dimensional rules worked out fairly well. Unfortunately it requires at LEAST 7 rules ( more rules makes the algorithm a little clearer and neater ). Worse, Bowers uses very wordy and illustrative explanations for the rules. None the less, I have carefully studied dimensional arrays and they do work.

If you ask me, a number as impressive as gongulus deserves to be in the Guinness Book of world records for something. True, it's so large that even mathematicians have no use for it !! But that's what makes it so impressive. The Guinness Book should have an entry on Jonathan Bowers as the creator of the worlds fastest growing computable functions, and in the entry gongulus should be mentioned just for kicks ( It would then be the largest number recognized in a professional piece of literature ). Then when bloggers ask "whats the largest number?" instead of just hearing about googolplex and Graham's someone will inevitably have to mention gongulus just to be a smart ass :)

Gongulus unlike googolplex and Graham's however is not so easy to explain. It requires notation and concepts that require some real imagination to understand. Even here I've only given a cursory explanation for how they work. They are both surprisingly simple to explain, and surprisingly difficult to define rigorously. For this reason it may never be as popular as googolplex and Graham's Number. But I really don't think that's the reason it is not recognized. The gongulus just needs to proper exposure and recognition (that's what this article is here for!). It really is a legitimate number using legitimate mathematics.

Professional mathematicians simply regard the art of creating large numbers for their own sake as trivial. They might appreciate it as an impressive computable function, but to them anything computable is trivial because the Busy Beaver function "grows faster than any computable function". This maybe so, but this oft repeated phrase overshadows the fact that the more complex the computable function, the more states are required to surpass it. Bowers has certainly increased the complexity of known computable functions, and taken them to a new frontier.

I've heard it said that before you would reach BB(100) the resourcefulness of the human imagination would be overwhelmed. Is this so? A gongulus already seems pretty complex. Just how close is it to something like BB(100)? The world may never know, but at least once mathematicians need a handy way to express BB(10) or BB(20), Bowers notations will already be on hand! That's got to count for something.

In any case, even if the gongulus is not officially recognized, and even if it is complicated, I still think people would like to hear about it. Numbers are the domain of everyone who is interested in them, so who cares what Guinness says, gongulus IS one of the WORLDS LARGEST NUMBERS period.

It's so large in fact, that it knocks Guinness "world champion" right out of the list of contenders! In fact it gets completely crowded out because Bowers goes even further than this! He starts talking about Super dimensional arrays, Trimensional arrays, tetrational arrays , pentational arrays , etc.

Some of these numbers are so large that Bowers can't fully explain them. Even he doesn't fully understand them, and he comments " how do these arrays work ? only God knows ...".

The largest number Bowers has coined was finally given a definition on March 13 , 2008 . The number is called the "meameamealokkapoowa oompa" and it could very well be the largest number in the world. You really can't overstate how huge this number is. Unfortunately it literally defies explanation, and so it would be hard to convince a professional mathematician that such a number exists (Technically speaking its not the number that doesn't exist, but rather the name fails to signify a number if the function is not well defined).

For this reason I think gongulus has a better chance making it in the Guinness Book of World Records, as the largest number defined through the use of an algorithm. Then every time someone blogs about Large Numbers we'll hear about gongulus in addition to googolplex and Graham's Number. Of the three of these, the largest would be the only one coined by an amateur mathematician :)

Then again, it doesn't need to be in Guinness to become well known. We live in the information age where memes can replicate themselves through blogs and chat rooms. Next time someone ends a large number conversation with Graham's Number, you can always top them and try to explain gongulus. If it gets brought up often enough it might eventually become officially recognized. Then you'll find it in the dictionary a little before googolplex under G. Websters will probably have to settle for the abbreviated definition " An extremely large number defined by Jonathan Bowers", rather than an exact definition since that would require a couple pages of mathematics ! :)

If you find this stuff interesting and want to learn more you can visit Jonathan Bowers new website ...

http://www.polytope.net/hedrondude/home.htm

Be warned though, that Bowers does not sufficiently explain his notation, so one can only speculate about what he means at times. Thankfully Bowers work is being deciphered by others. Sam Hughes also has studied array notation and explains how dimensional arrays work. He has a series of "everything 2" articles where he explains various levels of array notation up to and including arbitrary dimensional arrays. ( You can also find a compact form of gongulus at the end of the articles ).

http://everything2.com/e2node/Linear%2520array%2520notation

Chain arrows arrived on the public scene in 1996, in the well known "The Book of Numbers". In a way you could consider John Conway, the inventor of Chain arrows, as the "Number Champ" at the close of the 20th Century. If this is so then Jonathan Bowers and his arrays represent the dawn of the 21st Century. Interestingly he is a testament to the power of the information age. An amateur mathematician who would otherwise be unknown is able to present his ideas to the world through the web. These are the Extremely Large Numbers of the 21st Century ! ... and the game has only just begun ...

-- Sbiis Saibian

1 comment:

Giga said...

You really have a gift of explaining this Big number stuff!
I am deciphering Bowers' plans for nested arrays myself. You are right that the Gongulus is the largest number that is clearly defined on his website. But the extra-dimensional nesting holds a Big promise.

About the arrogance of mathematicians and the Busy Beaver:
The Beaver depends on its Turing Machine, and the TM uses a translation of mathematical signs to numbers. So if you could count signs directly with a Big number this defines a maximal TM.

For example functions can be defined with 2 characters (1 and ,) and Bowers nested arrays start using 3 (the nesting count ;.. is separate from the dimension count ,..) and so on...
But as we know it all boils down to the base a,b to create even bigger TM and this is only the first hyperarithmetical hierarchy.

Kind regards
Asamkyeya dasa