Comparing Moser Notation With Conway Notation

Wednesday, January 5, 2011

This post has undergone serious revision on May 15, 2011, in response to comments I’ve received.

A long time ago, a reader named Louis Epstein asked a question about large numbers. In continuing my very weird hobby of mathematically defining very large numbers, I have decided to answer his question in a separate post.

He asks:

What about Moser polygons,considered the step beyond Conway arrows at Susan Stepney’s site?…I’d like to see a good comparison between 3→3→3→3 and
3[3[3[3]]]] (i.e. 3[3[27]]])…both are way bigger than Moser’s Number but are they both bigger than Graham’s?

 

So we’re tasked with comparing 3→3→3→3, originating from Conway Chained arrow notation (explained by me here), with 3[3[3[3]]]], coming from a notation used by Susan Stepney on her site for extending Steinhaus-Moser notation, commonly referred to as just Moser notation.

But first, what is all of this 3[3[3[3]]]] business?

 

From Moser Notation to Stepney Extensions

Steinhaus defined the following method of making fairly large numbers:

  • a number n in a triangle equals n^n. 3 in a triangle = 3^3 = 27
  • a number n in a square equals that number in n triangles, all of which have to be un-nested. 3 in a square = ((3^3)^(3^3))^((3^3)^(3^3)) = (27^27)^(27^27) = …
  • a number n in a circle equals that number in n squares, all of which have to be un-nested.

 

Clearly the circle is already getting us rather large numbers. But this wasn’t enough — Moser came along and extended it with further rules:

  • all of the previous rules hold, except the following two
  • the circle is redefined to be the pentagon
  • a number n in a polygon of any amount of sides is that number in n nested polygons, all of which have one less side.

 

We now need a way to define this system in a way that is more easily writable. This is where Stepney’s Notation comes in. She defines the following: a[b]c = the number “a” in “c” polygons, each of which has “b” sides.

More formally, we can rewrite that as a stand-alone notation.

  • a[b]0 = a[2]c = a[1]c = a[0]c = a
  • a[b] = a[b]1
  • a[3] = a^a
  • a[b] = a[b-1]a
  • a[b]c = (a[b]c-1)[b]

 

The true advantage of this system is that it can get very large by nesting within the b value. Though Moser only went as far as notating Moser’s Number, which is 2[2[5]], or 2 in a polygon with “2 in a pentagon” sides, Louis defined something even larger. 3[3[3[3]]] is three in a “three in a “three in a triangle”-sided polygon”-sided polygon.

 

From Initial Values to Intractable Calculations

Now we can do some comparisons. Our end goal is to compare 3→3→3→3 and 3[3[3[3]]]], and see which is larger. The first problem is that 3→3→3→3 and 3[3[3[3]]]] are both intractable, which in this situation means they cannot possibly be calculated to their numerical value in scientific notation.

So let’s do a few minor comparisons first. Let’s compare 3[3] with 3→3.

3[3] = 3^3
3→3 = 3^3

So, 3→3 = 3[3].

 

Now let’s compare 3[3[3]] with 3→3→3.

3[3[3]] = 3[3^3] = 3[27] = 3[26]3 = (3[26]2)[26] = ((3[26])[26])[26] = …

3→3→3 = 3→(3→2→3)→2 = 3→(3→(3→1→3)→2)→2 = 3→(3→3→2)→2 = 3→(3→(3→2→2)→1)→2 = 3→(3→(3→2→2))→2 = 3→(3→(3→(3→1→2)→1))→2 = 3→(3→(3→3))→2 = 3→(3→27)→2 = …

So that would be comparing “”3 in a 26-sided polygon” inside a 26-sided polygon” inside a 26-sided polygon to “3 cubed”, 3^27 times. See how difficult this can be to figure out which notation creates the largest number?

We’re going to have to leave this question unanswered and instead adopt a different approach.

 

Using Limit Functions to Understand 3[3[3[3]]]

Luckily, we have something better to compare things with:

f^h(j) = \underbrace{f(f(f(f(f( \cdots f(f(f(j)))))) \cdots )))))}_{ \text{h nested functions}}

f_2(j) = f^j(j)

f_2^h(j) = \underbrace{f_2(f_2(f_2(f_2( \cdots f_2(f_2(j)))))) \cdots )))))}_{ \text{h nested functions}}

f_k(j) = f_{k-1}^j(j)

f_{\omega}(j) = f_j(j)

f_{\omega}^h(j) = \underbrace{f_{\omega}(f_{\omega}( \cdots (j)))) \cdots ))}_{ \text{h nested functions}}

f_{\omega+1}(j) = f_{\omega}^j(j)

f_{\omega+2}(j) = f_{\omega+1}^j(j)

Again, if you are confused, please refer to the sections in the Big Number series.

 

Basic Moser Notation to Limit Functions

Now to make a limit function representation of 3[3[3[3]]]. To do this, we will turn it into a variation on a base function m(x). But what is m(x) and what is it’s base?

It turns out the base is m(x) = x^x because the entire notation will eventually result in a number in a lot of triangles, and a number in a triangle is that number to the power of itself. So we establish our base function:

x[3] = m(x) = x^x

 

Now what happens when we extend this to any number of triangles? It simply iterates the base function.

\text{x[3]c} = m^c(x) = \underbrace{m(m(m(m(m( \cdots m(m(m(x)))))) \cdots )))))}_{ \text{c nested functions}}

And since the square merely repeats the triangles, we know that:

\text{x[4]} = \text{x[3]x} = m^x(x) = m_2(x)

And we know that extending it to c squares will merely iterate this function.

\text{x[4]c} = m_2^c(x) = \underbrace{m_2(m_2(m_2( \cdots m_2(m_2(x))) \cdots ))}_{ \text{c nested functions}}

And then the value for the pentagon becomes clear.

\text{x[5]} = \text{x[4]x} = m_2^x(x) = m_3(x)

 

Now let’s make another big jump. We have enough of a pattern to see what happens when we extend this to a polygon of any amount of sides.

\text{x[b]} = \text{x[b-1]x} = m_{b-3}^x(x) = m_{b-2}(x)

 

Finally the full 3[3[3[3]]]

How does this work with 3[3[3[3]]]? Well we can build it into limit functions one step at a time.

Since 3[3] = m(3), that means 3[3[3[3]]] = 3[3[m(3)]]

\text{3[m(3)]} = m_{m(3)-2}(3) \text{, therefore 3[3[3[3]]]} = \text{3[} m_{m(3)-2}(3) \text{]}

\text{3[} m_{m(3)-2}(3) \text{]} = m_{m_{m(3)-2}(3)-2}(3) \text{, therefore 3[3[3[3]]]} = m_{m_{m(3)-2}(3)-2}(3)

 

Using Omega

However we can rewrite that using the limit symbol ω. Consider:

m_{\omega}(3) = m_3(3)
m_{\omega+1}(3) = m_{\omega}^3(3)
= m_{\omega}(m_{\omega}(m_{\omega}(3))) = m_{\omega}(m_{\omega}(m_3(3)))
= m_{\omega}(m_{m_3(3)}(m_3(3)) = m_{m_{m_3(3)}(m_3(3)}(m_{m_3(3)}(m_3(3))

Therefore mω+1(3) > 3[3[3[3]]].

 

3→3→3→3 Using Limit Functions

Again, we first need a base function. Conway Notation operates differently than Moser Notation — while Moser Notation builds a very large amount of triangles, Conway Notation builds a very large power tower. Therefore our base function is going to be that power tower, made of 3.

c(x) = 3→x = 3^x

Now how does the second arrow change the picture? We know something like 3→x→2 will create a power tower of 3 that is “x” high, or 3^3^3^3^…^3 (x 3′s stacked). This means we are simply iterating the c() function x times.

3→x→2 = cx(x) = 3^3^3^3^…^3 (x 3′s stacked)

What about 3→x→3? Like upping the amount of sides in the notation, this is going to modify the size of the function like so:

3 \to x \to 3 = c_2^x(x)

And that makes it simple to see what 3→x→y does:

3 \to x \to y = c_{y-1}^x(x)

 

The Third Arrow

Now for the challenge. We need to add the third arrow. What is 3→3→x→2 in terms of the limit function?

3→3→x→2 = 3→3→(3→3→(x-1)→2) = 3→3→(3→3→(3→3→(x-2)→2)) = … = 3→3→(3→3→(…(3→3)…)), x layers deep.

This shows we’ve found that x will become the subscript of the function, or:

3 \to 3 \to x \to 2 = c_{\omega+1}(x)

Therefore, 3→3→3→2 = c3(3) = cω+1(3)

 

Now we finally have 3→3→3→3 in sight. What is 3→3→x→3? Let’s explore this by exploring what 3→3→2→3 is.

3→3→2→3 = 3→3→(3→3→1→3)→2 = 3→3→27→2 = 3→3→(3→3→26→2) = 3→3→(3→3→(3→3→25→2)→2)→2 = …

From this pattern, we can tell that:

3→3→2→3 = cω+1(3)

And therefore, 3→3→3→3 = cω+2(3)

 

From A Better Comparison to the Answer

So first we’ll compare the smaller challenge: 3[3[3]] vs. 3→3→3.

We know that 3[3[3] = mm(3)-2(3) and 3→3→3 = c23(3). Which is bigger?

Well, since m(x) is bigger than c(x) for each and every x, we know that ma(x) > ca(x).

However, this slight difference will not make up for the power of subscripts, so ca+1(x) > ma(x).

Since mm(3)-2(3) > c23(3), that means 3[3[3] > 3→3→3.

But does that hold up when we extend both notations a bit further?

 

We can compare 3[3[3[3]]] to 3→3→3→3 the same way.

\text{3[3[3[3]]]} = m_{m_{m(3)-2}(3)-2}(3) < m_{\omega+1}(3)

3 \to 3 \to 3 \to 3 = c_{\omega+2}(3)

c_{\omega+2}(3) > m_{\omega+1}(3)

3 \to 3 \to 3 \to 3 > \text{3[3[3[3]]]}

So there’s our answer. 3→3→3→3 > 3[3[3[3]]].

 

Comparing them Both to Graham’s Number

Louis Epstein raised a second question, however. How do these two numbers compare to Graham’s Number?

Graham’s Number (explained in detail here) is a function that works like this:

g(1) = 3→3→4
g(2) = 3→3→(3→3→4)
g(x) = 3→3→g(x-1)
Graham’s Number = G = g(65)

This kind of recursion is the same done by 3→3→x→2, which is 3→3→(3→3→(x-1)→2).

This means that G is just slightly smaller than 3→3→65→2. Since 3→3→3→3 is definitely bigger than 3→3→65→2, 3→3→3→3 > G.

But what of 3[3[3[3]]], which is smaller? Is it so much smaller that it’s not as large as G?

 

G vs. 3[3[3[3]]]

There are a variety of ways to approach this comparison, but I’m going to do it not by comparing G and 3[3[3[3]]] but by comparing G and 3→3→65→2.

We found out that 3→3→x→2 = cω+1(x), therefore 3→3→65→2 = cω+1(65)

We know from our previous calculations that:

\text{3[3[3[3]]]} = m_{m_{m(3)-2}(3)-2}(3) < c_{\omega+1}(3) < G

Therefore, 3[3[3[3]]] is not as big as Graham's Number.

In conclusion, 3→3→3→3 > G > 3[3[3[3]]]

Continued by: Conway and Moser Revisited

Be Sociable, Share!

 

Liked this Essay?

7 Comments (RSS)

Read them below and add one yourself.

  1. Louis Epstein says:
    Thursday, January 6, 2011 at 11:55 pm

    Thank you for the investigation!…I note that your result is more flattering to 3[3[3[3]]] than was my inference from Tim Chow’s proof that G>M.

    The broader issue of the relative power of Conway and Moser notations is not yet clear,though.Does the relationship hold for all values of x[x[x[x]]] vs x->x->x->x or for all numbers of arrows vs. polygon-nestings of repetitions of a given x?

    In defining the “popble” (point,polygon,blast) function for my linked site,I assumed the maximum value of the function would be through ordering the operations Knuth,Conway,Moser,Bowers since Stepney represented Moser as the step beyond Conway.(I assume you are familiar with Chris Bird’s proof that beyond 4 terms,even a linear Bowers array beats a Conway chain).If Conwaying beats Mosering I guess an even higher value would be reached with Knuth,Moser,Conway,Bowers order,though I am not going to redefine the function,it seems such a natural progression from the two-term Knuth expression to the long line of Conway arrows to the planar Moser polygon to the Bowers array of as many dimensions as the Moser expression of each popble-cycle yields.
    Further readings:
    http://uglypc.ggh.org.uk/chrisb/maths/super_huge_numbers/
    http://www.polytope.net/hedrondude/array.htm
    I assume that the Meameamealokkapoowa Oompa was created to trump Bird’s Number,I am not sure how high up the chain my own page’s named numbers have reached but as I state,Bowers himself admits that the number 2,popbled,”easily beats a gongulus”,one of his “Infinity Scrapers”.My named numbers only use popblings (never only one) to determine the sizes of power towers through multiple functions.

  2. Peter says:
    Friday, January 7, 2011 at 12:17 am

    I’ll do some more analysis in future posts, perhaps to compare Moser and Conway once and for all. Once I have my limit function notation written far enough, I’ll also run through everything Bird has ever defined and show how it’s smaller.

    From my initial guess, I’d have to say that if you switched step 3 with step 4, popbled numbers would be bigger.

  3. Louis Epstein says:
    Friday, January 7, 2011 at 1:39 am

    Bowers and Bird have clearly one-upped each other over the years,Bird’s email address at that linked site does not work so I don’t know if he’ll come charging back.I do intend to extend my own system further but comparisons (including to XKCD-forum entrants) do get difficult.

  4. Peter says:
    Friday, January 7, 2011 at 2:21 am

    I’m not sure if you know this, but I am myself one of the XKCD-forum entrants, eggdudeguy. The system I intend to describe will eventually end up being the entire ordinal collapsing notation available there, though not written in a manner that can be easily understood. I’d recommend starting at about page 17 and read all the way through.

    http://forums.xkcd.com/viewtopic.php?f=14&t=7469&start=640

  5. Louis Epstein says:
    Friday, January 7, 2011 at 3:08 pm

    I believe I originally located you through your XKCD postings.Of course,the rules prevent me from just putting your latest “Deedlit-Eggdudeguy Number” in a 5[5[5[5[5]]]]-sided polygon and popbling it.But I’m mainly focussed on extending nomenclature into the upper beyond.

  6. chasrob says:
    Friday, February 25, 2011 at 12:22 pm

    Slightly OT, but if you want to calculate some of the tinier nummbers mentioned, like 3 in a square = ((3^3)^(3^3))^((3^3)^(3^3)) = (27^27)^(27^27) =??????
    Here’s a javascript Hypercalc that won’t overflow up to ten tetrate 10^308–http://ylmass.edu.hk/~mathsclub/HyperCalc/HyperCalc.html

    I get 10^(1.7137024398162594 × 10^40)!

  7. Deedlit says:
    Saturday, April 16, 2011 at 3:17 am

    Hi Peter! Long time no talk.

    Just popping in to make a correction: Graham’s number is bigger than 3[3[3[3]]]. The error seems to come from the following line:

    3→3→x→2 = 3→3→(3→3→(x-1)) = 3→3→(3→(3→2→(x-1))→(x-2)) = 3→3→(3→3→(x-3)).

    Actually, it should be

    3→3→x→2 = 3→3→(3→3→(x-1)→2) = 3→3→(3→3→(3→3→(x-2)→2)) = 3→3→(3→3→(…(3→3)…)) with x nestings.

    This is c_c_c…c_27 (1)…(1)(1)(1) with x-1 c’s, or approximately c_(w+1)(x). Thus Graham’s number is approximately c_(w+1)(64), and hence larger than 3[3[3[3]]]. Graham’s number is between 3[3[3...[3]…]] with 65 3′s and 3[3[3...[3]…]] with 66 3′s.

    Some miscellaneous corrections:

    3^^x = 3^3…^3 with x 3′s = c^x(1), not c^x(x). So we need to modify the general definition of c_n(x) to

    c_(n+1)(x) = c_n^x(1)

    to give us

    3→x→n = c_n(x).

    3→3→2→3 = 3→3→27→2 = c_c_…_c_27 (1)…(1)(1) with 26 c’s, which is between c_(w+1) (26) and c_(w+1) (27).

    3→3→3→3 > c_(w+2) (3), but it’s a pretty good approximation;
    ‘
    3→3→x→3 is between c_(w+2)(x) and c_(w+2)(x+1)

Leave a Reply

Comment HTML: You can use HTML in comments. I reccomend <blockquote>Quote</blockquote> for quoting what others have said. <b>Text</b> is for bold, <i>Text</i> is for italic, and <a href="url">text</a> is for making links.