2.10. Extensions to Conway Chain Arrows
Introduction
In the previous article we learned about Conway chain arrow notation, the most powerful "popular" large number notation. But now we'll look at people have extended upon Conway chain arrows to make the notation more powerful. Although I don't really consider extensions to chain arrows a "popular" large number notation like Knuth's up-arrows and the like, in my opinion discussing such extensions fits better among section 2's content than later sections.
There are a few people who have taken the task of extending Conway chain arrows. Here we'll be looking some of those extensions: the CG function, Peter Hurford's higher-level chains, Peter Hurford's C function, and an improved version of Hurford's extended chain arrows.
The CG Function
Conway and Guy, in their Book of Numbers where they introduce chained arrow notation as I discussed in the previous article, also bring up a sequence of numbers that is closely related to the Ackermann numbers (the sequence 1^1, 2^^2, 3^^^3, 4^^^^4, etc.) but even faster-growing. The sequence is:
1
2->2
3->3->3
4->4->4->4
etc.
That is a pretty cool sequence alright, and it is today known as the Conway numbers on analogy with the Ackermann numbers.
The first two members (1 and 2->2) are trivial, as they evaluate to 1 and 4 respectively.
The third member (3->3->3), however, is much larger, as it's equal to 3^^^3 in up-arrow notation, which evaluates to a power tower of 7,625,597,484,987 threes (it's a personal favorite large number of mine). But it's still a number that can be expresed in up-arrow notation.
The fourth member (4->4->4->4) is the first number in the sequence that really needs you to bring out a new notation to express (namely Conway chain arrows themselves). It's a pretty awesome number as we saw in the previous article when we visualized it using Knuth's up-arrows, and it is in fact the largest number that is mentioned in Conway and Guy's book at all.
After that comes the fifth number (5->5->5->5->5, super-unfathomable), the sixth number (6->6->6->6->6->6, utterly super-unfathomable), and so on. Why not jump to the 100th member of the sequence, or the googolplexth member - no wait, the Nth member where N is Graham's number! Now that is an awesome number!
In fact, this sequence can be generalized to a function that is often noted cg(n) (cg stands for Conway and Guy), which is equal to n->n-> ... ->n->n with n n's. With that function we can generate numbers larger than ANY we've previously encountered! For example, on the second page of the xkcd forums' thread My number is bigger!, a user named "Mouffles" came up with the number cgG(G) where G is Graham's number (remember that fn(x) is f(f(...(f(x))...))) with n copies of f). That would evaluate to:
cg(cg(cg(cg(cg( ... ... ... ... cg(cg(G64)) ... ... ... ))))))
with Graham's number of copies of cg
which itself evaluates to:
cg(cg(cg(cg(cg( ... ... ... ... cg(G64 -> G64 -> ... ... ... -> G64 -> G64) ... ... ... ))))))
where there are Graham's number minus 1 copies of cg and Graham's number of G64's in the chain
Now the chain of Graham's number of Graham's numbers is itself an utterly unimaginable number (far scarier than Graham's number mind you!), and that's just applying the first cg to Graham's number - imagine how long it would take to evaluate the other Graham's number minus one cg's!!!
All this recursively applying the cg function may seem like we're completely blasting into the stars ... until you consider that this is just one level of recursion applied to a function with already high levels of recursion! Why is that important? You will see as we examine a much better extension of Conway chain arrows: Peter Hurford's extended chain arrows.
Peter Hurford's Extensions to Chain Arrows
An extension to Conway chain arrows was devised by Peter Hurford on his blog, in a series of posts about large numbers, starting from simple recursive functions and going all the way up to the large Veblen ordinal in the fast-growing hierarchy, a realm of the numberscape beyond even what we'll discuss in section 3 and maybe section 4! Unfortunately those blog posts were for whatever reason taken down from the Internet, but you can still read them on the web archive here.
Here we'll focus on part 2 of his series of blog posts, where Hurford discusses Graham's number, Conway chain arrows, and his extended chain arrows, the last of which we'll examine now.
The Second Level of Chain Arrows
Hurford explains that we can extend chain arrows first by defining a->2b = a->a->a ... ->a with b right-arrows. However, his usage of that equality is confusing because in one example he gives, 3->23 evaluates not to 3->3->3->3 (three right arrows), but to 3->3->3 which only has two right arrows. This may seem simply like an error, but consider this: the equality 3->23 = 3->3->3 makes a good amount of sense when you consider that 3->3->3 has three threes rather than three arrows. Perhaps Hurford's usage of "b right arrows" rather than "b copies of a" was inspired by the equality a->b->c = a^^^...^^^b with c ^s. But on the other hand "b copies of a" makes more sense if you consider that (for example) a^^b is a^a^a^a^a......^a^a with b copies of a, not with b ^s.
So is "b copies of a" what Hurford meant, or was it "b right arrows"? He apparently thought the two meant the same thing, which is clearly not true - for example, 3->3->3->3 has three right arrows but for copies of 3. Although he defined it as using b right arrows, by the usage of his examples he was clearly meaning something more like "b copies of a", and therefore that's what a->2b will mean for our purposes.
We can generalize a->2b to any expression of the form a->2b->2c ... ->2z, with any amount of numbers in the chain, by using the same recursive rules we used in plain old Conway chain arrows. That can be thought of as a second level of chain arrow notation! We can define that extension using the ruleset:
Rule 1 (only two numbers): a->2b = a->a->a ... ->a with b copies of a
Rule 2 (last number is 1): #->21 = # where # denotes the rest of the chain
Rule 3 (second last number is 1): #->21->2a = # where # denotes the rest of the chain
Rule 4 (otherwise): #->2a->2b = #->2(#->2(a-1)->2b)->2(b-1)
These rules are identical to the normal rules for chain arrows except for rule 1. Because of that, it should be easy to see how the "second level" of chain arrows works if you understand the normal chain arrows. But we still will examine some numbers this extension to chain arrows can make, to get a feel for how much more powerful it is than merely iterating the C function.
One important thing to note before we continue: In Hurford's extended chain arrows, you can't have an expression of the form a#b#c# ... #z where the #s aren't either all ->s or all ->2s. This means that expressions like 3->23->3 or 10->53->2100->20 are illegal. However, expressions like 3->2(3->3) are legal, since that just evaluates to 3->227 which is a legal expression.
Now we're ready to look at some examples. Let's take the simple and non-trivial second-level chain:
3->23->22
That evaluates to:
3->2(3->22->22)->21
= 3->2(3->22->22)
= 3->2(3->2(3->21->22)->21)
= 3->2(3->2(3->21->22))
= 3->2(3->23)
= 3->2(3->23)
= 3->2(3->3->3)
= 3->3->3-> ... ... ... ... ... ... ... ->3->3, with 3->3->3 = 3^^^3 threes
Hm, this is a pretty big number, but still not something that really transcends recursion of the CG function or even having a large number of numbers in the Conway chain. Let's try instead the chain 3->24->22. That would equal:
3->2(3->23->22)->21
= 3->2(3->23->22)
= 3->2X where X is 3->3->3-> ... ... ... ... ... ... ... ->3->3 with 3^^^3 threes
= 3->3->3-> ... ... ... ... ... ... ... ->3->3 where the number of 3's is 3->3->3-> ... ... ... ... ... ... ... ->3->3 where the number of threes is 3^^^3
Now this is a better number alright! It's not just a 3^^^3-number chain, but a 3^^^3-number-chain-number-chain. But still, it's easy to get this far with just the CG function. How about:
3->23->23
Evaluating THAT gives us:
3->2(3->22->23)->22
= 3->2(3->2(3^^^3))->2
How big is that?! To understand its size we need to use a stage idea:
Stage 1 = 3->21->22 = 3
Stage 2 = 3->22->22 = 3->3->3 = 3^^^3
Stage 3 = 3->23->22 = 3->3->3-> ... ... ... ... ... ... ... ->3->3 with Stage 2 (3^^^3) threes
Stage 4 = 3->24->22 = 3->3->3-> ... ... ... ... ... ... ... ->3->3 with Stage 3 threes
...
This number is then stage 3->2(3^^^3), aka stage 3->3->3-> ... ... ... ... ... ... ... ->3->3 with 3^^^3 threes. Now think about that for a second. We're not only going to the Graham's numberth stage (that would only take us to a number comparable to Mouffles' number from "My number is bigger!"), but to the Xth stage where X is a Conway chain of 3^^^3 threes!!! Graham's number, by contrast, can be approximated using a mere 4-number chain (specifically as 3->3->64->2, an approximation for Graham's number). This totally crushes that iteration of the C function, but that's saying nothing of monsters like:
3->23->23->23
which solves to:
3->23->2(3->23->22->23)->22
= 3->23->2(3->23->2(3->23->21->23)->22)->22
= 3->23->2(3->23->2(3->23)->22)->22
= 3->23->2(3->23->2(3->3->3)->22)->22
= 3->23->2(3->23->2(3^^^3)->22)->22
At this point all we can say about this number is that it's INSANE. And that's saying nothing of a number like:
3->23->23->2 ... ... ... ... ... ... ... ->23->23 with 3->23->23->23 threes
Can things get any CRAZIER than this?!?! Yes they can - we can further extend upon the "second level" of chain arrows by introducing the ->3 arrow!
The Third Level and Beyond
By introducing the ->2 arrow, it's only natural to devise a ->3 arrow, which is to the ->2 arrow what the ->2 arrow is to the -> arrow. In other words:
a->3b = a->2a->2a->2 ... ... ... ... ... ... ... ->2a->2a with b copies of a
Likewise, we can adopt the rules for normal and second-level chain arrows for the third-level chain arrows. For example:
3->33->32
= 3->3(3->32->32)->31
= 3->3(3->32->32)
= 3->3(3->3(3->31->32)->31)
= 3->3(3->3(3->31->32))
= 3->3(3->33)
= 3->3(3->23->23)
= 3->23->23->2 ... ... ... ... ... ... ... ->23->23 with 3->23->23 threes
As you can see, even this tiny example of a third-level Conway chain produces an insanely huge number. In fact, there's NO NEED to stop at a third level of chain arrows. We can make a fourth level:
a->4b = a->3a->3a->3 ... ... ... ... ... ... ... ->3a->3a with b copies of a
and even generalize this to:
a->xb = a->x-1a->x-1a->x-1 ... ... ... ... ... ... ... ->x-1a->x-1a with b copies of a
to go to the googolth, or Graham's numberth, or 3->33->32, or whatever, level of Conway chain arrows. With that we can make a generalized definition of Hurford's extended chain arrows.
Generalized Definition of Hurford's Extended Chain Arrows
Rule 1 (only two numbers, first level of chain arrows):
a->1b = ab
Rule 2 (only two numbers, second or higher level of chain arrows):
x > 1: a->xb = a->x-1a->x-1a ... ->x-1a with b copies of a
Rule 3 (last number is 1):
#->x1 = # where # denotes the rest of the chain (chop off the ending 1)
Rule 4 (second last number is 1): #->x1->xa = # where # denotes the rest of the chains (chop off the last two numbers)
Rule 5 (otherwise): #->xa->xb = #->x(#->x(a-1)->xb)->x(b-1) (decrease last number by 1, feed chain with second last number decreased by 1 into the second last number)
This above is an elegant set of 5 rules that can be used to evaluate any expression in Hurford's extended chain arrows. Note that ->1 is just a synonym of ->. These already produce some staggeringly large numbers ... but Peter Hurford decides to take his extended chain arrows a step further with his 3-argument C function.
Hurford's C Function
Hurford devised a C function that extends upon his subscripted chain arrows that can take anywhere from one to three arguments. He gives the ruleset:
C(a) = a→aa
C(a, 1) = a→C(a)a
C(a, b) = a*→C(a, b-1)a
C(a, 1, 1) = C(a, C(a, a))
C(a, b, 1) = C(a, C(a, b-1, 1))
C(a, 1, c) = C(a, C(a, a, c-1), c-1)
C(a, b, c) = C(a, C(a, b-1, c), c-1)
* he puts x there instead of a, clearly a typo
This is sort of like a mix of the Ackermann function and Conway's CG function, and it was probably inspired by the latter. Let's try some examples of this C function:
C(3) = 3->33 = 3->23->23 - that's a pretty awesome number we encountered early.
C(4) = 4->44
= 4->34->34->34
= 4->34->3(4->34->33->34)->33
= 4->34->3(4->34->3(4->34->32->34)->33)->33
= 4->34->3(4->34->3(4->34->3(4->34->31->34)->33)->33)->33
= 4->34->3(4->34->3(4->34->3(4->34)->33)->33)->33
= 4->34->3(4->34->3(4->34->3(4->24->24->24)->33)->33)->33
and so on ... imagine how huge this number is!
On analogy with the Conway numbers referring to the sequence of numbers a->a->a-> ... ->a with a copies of a (or a->2a for short), I'll call members of the sequence of numbers a->aa the Hurford numbers. They're an ever cooler and faster-growing sequence than the Conway numbers, as we just looked at the third and fourth Hurford numbers.
I think the one-argument C function is pretty simple. Now on to two arguments:
C(3,1) = 3->C(3)3 = 3->3->23->233
Already this is outrageously huge! But let's try something like:
C(3,3)
That would be equal to 3->C(3,2)3 = 3->3->C(3,1)33 = 3->3->3->3->23->23333.
That's an INSANELY HUGE number! Even the "level" of chain arrows this number uses is really hard to get straight even in terms of its level of chain arrows.
Hurford continues his two-argument C function with a 3-argument C function. Here are some examples:
C(3,1,1) = C(3,C(3,3))
To envision this number, imagine that stage 1 is C(3,1) = 3->3->23->233, (already ridiculously huge!), stage 2 is C(3,2) = 3->(stage 1)3, stage 3 = C(3,3) = 3->(stage 2)3, and continue all the way up to the Nth stage, where N is stage 3 (the huge number equal to 3->3->3->3->23->23333)!!!
C(3,2,1) = C(3,C(3,1,1)) = C(3,C(3,C(3,3)))
To imagine this number, go back to the stages used to imagine C(3,1,1), but this is the C(3,1,1)th stage!
C(3,1,2) = C(3,C(3,3,1),1)
If stage 1 is C(3,1,1), stage 2 is C(3,2,1), stage 3 is C(3,3,1) [that's stage C(3,2,1) in the stages used to imagine C(3,1,1)], and so on, then this is the C(3,3,1)th stage! Despite how awesome this is, this is still just the beginning ...
C(3,3,2) = C(3,C(3,2,2),1) = C(3,C(3,C(3,1,2),1),1)
To envision this number, go back to the stages to imagine C(3,3,2), but this is not just the C(3,3,1)th stage, but the stage C(3,1,2)th stage! As you can see this is utterly unfathomable.
One last example:
C(3,3,3)
= C(3,C(3,2,3),2)
= C(3,C(3,C(3,1,3),2),2)
= C(3,C(3,C(3,C(3,3,2),2),2),2)
= C(3,C(3,C(3,C(3,C(3,2,2),1),2),2),2)
= C(3,C(3,C(3,C(3,C(3,C(3,1,2),1),1),2),2),2)
= C(3,C(3,C(3,C(3,C(3,C(3,C(3,3,1),1),1),1),2),2),2)
= C(3,C(3,C(3,C(3,C(3,C(3,C(3,C(3,2,1)),1),1),1),2),2),2)
= C(3,C(3,C(3,C(3,C(3,C(3,C(3,C(3,C(3,1,1))),1),1),1),2),2),2)
= C(3,C(3,C(3,C(3,C(3,C(3,C(3,C(3,C(3,C(3,3)))),1),1),1),2),2),2)
= C(3,C(3,C(3,C(3,C(3,C(3,C(3,C(3,C(3,3->C(3,2)3))),1),1),1),2),2),2)
= C(3,C(3,C(3,C(3,C(3,C(3,C(3,C(3,C(3,3->3->C(3,1)33))),1),1),1),2),2),2)
= C(3,C(3,C(3,C(3,C(3,C(3,C(3,C(3,C(3,3->3->3->3->23->23333))),1),1),1),2),2),2)
...
Alright, this is just a crazy huge number.
Despite how insane these numbers are, the 3-argument C function isn't really that good an extension to Hurford's extended chain arrows! Wait, how can that be?! We will be able to see why when we examine the fast-growing hierarchy in section 3 and compare it against other notations.
There is one more trick that can be used to improve upon Hurford's extended chain arrows, and that is by improving the notation itself.
Improving Hurford's Extended Chain Arrows
Googology Wiki, on its article on Conway chain arrows, discusses Conway's notation and Hurford's extended chain arrows. It also curiously mentions that we can get up to the order of ww in the fast-growing hierarchy if we allow mixing different types of arrows (i.e. ->, ->2, ->3, etc), as opposed to w3 for normal extended chain arrows (for reference, Conway chain arrows alone go up to the order of w2). But how exactly would we mix different types of chain arrows, and how would such a section work? In this subheading I'll look at just that, and give my own proposal for how to better extend Conway chain arrows. You can call it Cookie Fonster's extended chain arrows if you want.
To avoid confusion with Hurford's extended chain arrows, I'll use ->x in place of ->x. With that we can make the ruleset:
Rule 1 (only two numbers, arrow is ->1):
a->1b = ab
Rule 2 (only two numbers, arrow is ->x where x > 1):
a->xb = a->x-1a->x-1a ... ->x-1a with b copies of a
Rule 3 (three or more numbers, last number is 1):
#->x1 = #
Rule 4 (three or more numbers, last number is not 1 but second last number is 1):
#->x1->xa = #
Rule 5 (three or more numbers, last two numbers are not 1 and last arrow is ->1):
#->na->1b = #->n(#->n(a-1)->1b)->1(b-1)
Rule 6 (three or more numbers, last two numbers are not 1 and last arrow is ->x where x > 1):
#->na->xb = #->na->x-1a->x-1a ... ->x-1a with b copies of a
Note: -> is a synonym for ->1.
These six rules can easily take us to MUCH further heights than before. Let's try an example:
3->23->23
Note that the 3->23 should be read as 3, ->2, 3, NOT as 3->(23) (using ba to indicate a tetrated to b). That said we can evaluate that chain:
3->23->23
= 3->23->3->3 [rule 6]
= 3->23->(3->23->2->3)->2 [rule 5]
= 3->23->(3->23->(3->23->1->3)->2)->2 [rule 5]
= 3->23->(3->23->(3->23)->2)->2 [rule 4]
= 3->23->(3->23->(3->3->3)->2)->2 [rule 2]
= 3->23->(3->23->(3^^^3)->2)->2
As it turns out, this number is the same number as 3->23->23->23 using Hurford's extended chain arrows. In fact, there is the relationship:
a->2b-> ... ->z = a->2b->2 ... ->2z
For another example, let's try the number:
3->23->23->3
That evaluates to:
3->23->2(3->23->22->3)->2
= 3->23->2(3->23->2(3->23->21->3)->2)->2
= 3->23->2(3->23->2(3->23)->2)->2
= 3->23->2(3->23->2(3->3->3)->2)->2
= 3->23->2(3->23->2(3^^^3)->2)->2
Now focus on the number within the parentheses, 3->23->2(3^^^3)->2. That is MUCH bigger than 3->23->(3^^^3)->2. To imagine this number, think along these lines.
Stage 1 = 3->23->21->2 = 3->23 = 3->3->3 = 3^^^3
Stage 2 = 3->23->22->2 = 3->23->2(3->23->21->2) = 3->23->3-> ... ->3 with 3^^^3 + 1 threes
Stage 3 = 3->23->23->2 = 3->23->3-> ... ->3 with (Stage 2) + 1 threes
...
the number we're talking about here is the Nth stage, where N is the 3^^^3th stage!
Now stage 2 is also the same number as 3->23->2 ... ->23 with 3^^^3 + 1 copies of 3, or 3->3(3^^^3 + 1) for short. This means that the 3^^^3th stage is already a number that transcends the second level of chain arrows using Hurford's system, and that's itself much smaller than the number:
3->23->23->23
That evaluates to:
3->23->23->3->3
= 3->23->23->(3->23->23->2->3)->2
= 3->23->23->(3->23->23->(3->23->23->1->3)->2)->2
= 3->23->23->(3->23->23->(3->23->23)->2)->2
Let's try to compare this to the previous number, which equals 3->23->2(3->23->2(3^^^3)->2)->2. If we call the number 3->23->2(3^^^3)->2 X and the number 3->23->23->(3->23->23)->2 Y, then we get:
3->23->23->3 = 3->23->2X->2
3->23->23->23 = 3->23->23->2Y->2
Not only is Y much larger than X, it also is far larger than 3->23->23->3 itself! There's just no way we can comprehend any of these numbers. Let's move on to the third level of chain arrows with my system.
To get an idea of how insane the third level of chain arrows is with the refined extension of chain arrows, let's examine the number 3->33->33. It evaluates to:
3->33->23->23
= 3->33->23->3->3
= 3->33->23->(3->33->23->2->3)->2
= 3->33->23->(3->33->23->(3->33->23->1->3)->2)->2
= 3->33->23->(3->33->23->(3->33->23)->2)->2
= 3->33->23->(3->33->23->(3->33->3->3)->2)->2
= 3->33->23->(3->33->23->(3->33->(3->33->2->3)->2)->2)->2
= 3->33->23->(3->33->23->(3->33->(3->33->(3->33->1->3)->2)->2)->2)->2
= 3->33->23->(3->33->23->(3->33->(3->33->(3->33)->2)->2)->2)->2
= 3->33->23->(3->33->23->(3->33->(3->33->(3->23->23)->2)->2)->2)->2
= 3->33->23->(3->33->23->(3->33->(3->33->X->2)->2)->2)->2 where X is the huge number equal to 3->23->23 we encountered earlier
At this point there's nothing we can really say to understand the enormity of these numbers! Just imagine numbers at the fourth level or higher.
Conclusion
All those giant numbers extended chain arrow notation lets us generate might seem to be impossible to comprehend at all - not just impossible to comprehend their size, but impossible to imagine how they would compare against each other! These numbers likely seem to be insanely huge and blasting way beyond the stars! But are those the largest numbers humans can imagine, have we reached the end? Of course not. You should know by now that with the right tools (which we now have), when it comes to generating large numbers the sky is the limit, not something like a googolplex to the power of a googolplex (which we've now left way behind ourselves of course).
Besides, these numbers ARE NOT impossible to compare against each other. They may be difficult at the moment, but in section 3 we will examine more notations that will help us do such comparisons, and compare all our notations against each other. Those notations we'll examine in section 3 are largely as powerful, if not MORE powerful, than extensions to chain arrow notation, and also easier to understand!
For example, take Jonathan Bowers' linear array notation (that'll be the first notation for us to examine in section 3). It's a notation that takes any number of positive integers, separated by commas and put into curly brackets, for example {3,5,124,2,3}, and evaluates them to a large number. This resembles Conway chain arrows, doesn't it? Well it's a MUCH more efficient way to generate large numbers. 1-entry ({a}), 2-entry ({a,b}), and 3-entry arrays ({a,b,c}) in Bowers' notation are equivalent to 1-number, 2-number, and 3-number Conway chains, but after that Bowers' notation diverges greatly from Conway chain arrows.
Only 4-entry arrays ({a,b,c,d}) already produce numbers as large as Conway chain arrows do! Notice that with Bowers' arrays we only need 4 arguments to make the same kinds of numbers we can make with any number of arguments in Conway chain arrows! And it gets MUCH WORSE from there. 5-entry arrays ({a,b,c,d,e}) are comparable to Hurford's extended chain arrows, and arrays with any number of entries ({a,b,c ... z}) are at the same level of power as my improved version of Hurford's extended chain arrows.
So how exactly do we compare Bowers' arrays to Conway chain arrows and their extensions? That is a question for section 3. For now, let's review what we learned in section 2.