“On the shoulders of giant numbers”
http://www.allergrootste.com/big/book/ch3/ch3_0.html
bigΨ
bigΨ.I. Number operations
Ψ.3. Chained arrows versus subscripting
chapter 3.0, edit 0.2.9
published: 2011-04-29
updated: 2011-12-30
§3.0.1. Conway's initial chained arrows
A large party of men, with To'uluwa, the chief of Omarakana, went to Tuma.
They landed not far from the Modawosi stone, when they saw a man standing there.
They immediately identified him as Gi'iopeulo,
a great warrior and a man of indomitable strength and courage, who had died recently
in a village not more than five minutes distance from Omarakana.
When they approached, he disappeared, but they heard distinctly
"Bu kusisusi bala [You remain I shall go]"
– the usual form of "Good-by".
– Baloma, the Spirits of the Dead
The mathematician John Horton Conway is best known for his
Game of Life
and the big
symmetry groups,
which can be used to pack
oranges
in 24-dimensional space.
He got most satisfaction from his
discovery
of the
surreal numbers though,
constructed by playing Conway games
to fill in the gaps between Cantor's ordinal numbers ω1..
Here we work out a
passage
from
The Book of Numbers
written by Conway and Guy,
where Conway shoots off a chained arrow notation
ai→... {ai#n}
which (for chains with n>3 parameters)
formulates Big numbers far beyond
superpowers.
To give a hint of its capacity,
watch how the simplest of chained arrow expressions already increases with
Ackermann-type
function speed.
= a^..a {^#c} where c = aa+- {0^} = a×a-1
Conway modelled his chained arrows after
Donald Knuth's
up-arrows,
which we've introduced
before
as the arrow operation
a^...b
{^#c}
starting from multiplication at
c=0,
exponentiation at c=1,
tetration at c=2,
etc.
The principle that a superpower
^.. {#c1}
equals a repeated number of preceding operations
^.. {#c}
can be expanded to an arbitrary number of parameters,
which is how Conway invented his main rule for
chained arrows.
a^..(b+1) {^#c1} =
a^..(..a.)
{^#c #b#}
<=>
a→b1→c1 =
a→(.a)→c..
{a→(
#b#)→c
}
ai→...y1→z1 {ai→#n} =
ai→...(.ai→...)→z..
{ai→...(
#y#)→z
ai#n}
Conway and Guy's book doesn't tell what should happen with the single chained arrow
a→b
.
This is
commonly
interpreted to signify the powers a^b
(plausible, for then all R→1 = R
).
But can also be defined independently as multiplication
ab {0^}
(via reduction to a→b→0
as usual),
or as addition ab {0*}
maybe.
Conway's
formula
for the first row of chained arrows covers superpowers
and makes a separate axiom for the basic three parameters redundant.
We'll support the historical interpretation that
a→b
equals a^b
exponentiation
and let this two parameter case be the initial axiom.
Lo and behold! Here come the first four parameters of the archetypical operator function
called chained arrows.
- a→1 = a
- a→b1 = (a→b)a {0^} == a... {#b1 0^} = a**b1
-
a→b→1 = a→b
a→b→c→1 = a→b→c
-
a→1→c = a
a→b→1→d = a→b
-
a→b1→c1 = a→(a→b→c1)→c
a→b→c1→d1 = a→b→(a→b→c→d1)→d
We've presented Conway's notation in the same format as our operatorial functions
(see
bigE)
to make clear that chained arrow signs →
are more like
parameter separators ,
than like operators.
Normally operations are resolved in order of
precedence,
that is by operator size,
but the evaluation of variables separated by chained arrows
is the sole consequence of their position in the row,
much like parameters in a function.
§3.0.2. Our single operator subscript
A natural alternative to bridge the conceptual gap between operators
and functions is to create operator types
with coefficients in the form of subscripts.
Subscripted arrowheads are recursively enumerated operators
of a type which transcends superpower arrows.
Here are the initial steps over operator counter c
and
type counter d
of subscripted arrows with four parameters.
- a^1;b = a^...b {^#b}
- a^1;...b {^1;#c1} = a^1;.. ... {^1;#c a#b}
- a^d1;b = a^d;...b {^d;#b}
- a^d;...b {^d;#c1} = a^d;.. ... {^d;#c a#b}
At the very start operator subscripts are equivalent to chained arrows,
but when a>2 we promptly speed away.
In the example below, we conveniently use the
signs 2
and 3
in place of their representation in units 1..
2^d;...2 {^d;#c} = 1111 = 2→2→c→d = 4
3→3→2→2 =
3→3→(3→3) =
3^...3 {^#27}
<
3^1;^1;3
= 3^...(3^^^3) {^#3^^^3}
<
3→3→3→2 =
3^...3 {^#3^..3 ^#27}
<
3^2;3 =
3^1;...
{3#3^1;^1;3
}
This should give you an impression
of the respective strength of these notations.
Note that in our construction of subscripted majority arrows
^Rj;..
a sequence of operators with mixed subscripts such as
a^1;^b
does not
make sense yet.
§3.0.3. Conway's row of chained arrows
After the first 4 parameters the rest of Conway's chained arrows
follows easily.
Let the
wildcard R
substitute for a row of arrow→separated→parameters
of arbitrary length n>0.
John H. Conway
Princeton 1987
- R→1 = R
- R→1→z1 = R→1→z == R→1→1 = R
- R→y1→z1 = R→(R→y→z1)→z
Because a→b
= a^b
there are no restrictions on the range of values the two drop axioms
apply to. And the
main
axiom without condition y>0 implies that
R→0→z = 1
(true for exponentiation). Fits like a clockwork!
Interestingly, the right part of a row
L→1→R
== L→1→y→1
= L→1→y
= L
collapses on the position of the parameter value 1
.
Where only the left part L
can be kept,
this is a waste of expressive power or
resolution.
Let's translate Conway's chained arrow notation Can
to φ-function format. The right arrows allow us to order
a number of variables in a sequence and are thus equivalent
to comma separators inside a function. (This is not to say that arrows
↑
and →
cannot help
the lonely mathematician to connect ——→
his calculations on a sheet of paper.)
- Can_φ(ai,...) {ai#n} = ai→... {ai#n}
It seems a bit awkward that the last parameter z
wasn't count down to 0
which is the preferred initial index for our operatorial functions.
For the definition of multiple arrows however, this shows us the
natural way
to transcend Conway's single arrow notation.
By iterating directly over the length of his row of chained arrows
we open up to higher dimensions and enter the next class
{K.3}
of Big number functions.
In between the
function classes
already past by, and those still unheard of…
the initial Conway super-jump is forthcoming.
# Function class generation
All classes {K}
start with the unit 1
that is counted in class {K.0}
whose numbers are used as variables in further functions.
Plain repetition of a value is {K.1.0}
multiplication,
repetition of multiplication is {K.1.1}
exponentiation.
Each new repetition type is worked out as a row of operations,
defining the next function.
This closes class {K.1}
of primitive recursion,
starting point for the first
Ackermann jump
into a higher class {K.2.0}
of functions.
The strength of these jumps can be measured by a
grafting
technique, which shows that every next chained arrow
(past superpowers) is equally strong.
This determines the Ackermann-Conway
class of functions {K.2.d}
which in turn can be
covered
by the countable subscripted arrow
a^d;..b
of bigE (due to its superior
upload method).
After we've counted units one, superpower stars and Ackermann jumps,
in class {K.3}
the principle to count is…
grafting rows.
The change from {K.1}
to {K.2}
is to be the new principle of subclass,
which starts with a whole row grafted on Conway super-jumps of level
{K.3.0}
(¿and moves further?)
to define the first row of
bigE
and from there on
bigI...
John H. Conway must have hinted at a ψ-function of countable
super-chained arrows by describing its first 4 values in his imaginative
Book of numbers.
Similar to the way Ackermann had to jump from primitive recursion
{K.1}
, super-chained arrows cannot be expressed
by Ackermann-Conway {K.2}
recursions alone.
Past the Conway super-jump the Can_ψ
function addresses the length of a row of chained parameters directly.
The extension to a double →→
arrow-operator we've concocted is apocryphal,
yet appears to be a natural consequence of Conway's notation
(where R→1 = R
in {0^} context).
- a→b→1 = a*... {a#b} = a→.. ... {→#0 a#b 0^}
- a→b→..1 {→#c1} = a→.. ... {→#c a#b 0^}
- Can_ψ(a) = a→... {a#a} = a→a→→1
-
Can_ψ(i)
== { 1, 4, 3^^7625597484987,
4→4→(4→4→(4→4→256→3)→3)→3, .. }
The second rule counts chained arrows when c=1
and from this Can_ψ
follows at c=2 in the line below.
Of the numbers Conway mentions in his book
Can_ψ(4)
= 4→4→4→4
is already physically inexpressible
without resort to a function higher than superpowers.
§3.0.4. Our row of operator subscripts
By the same rules for subscripted operators
^d...
we saw
above,
comma separated coefficients can be extended naturally
right up to the end of a first row
^d,..,z...
But it's not so obvious how to handle the initial subscripts.
We'll use an upload method that was (to our knowledge)
first introduced by Jonathan Bowers in his
Exploding Array Function.
The concept that a low level parameter value is build up to seed higher parameters
is one of the most powerful rules for creating Big numbers.
Follow the functions of e
-init and e
-step which
substitute the value b
for c=1 and d=1
to resurrect these parameters after they are count down.
These are cases of what we call uploading.
- a^1,1;b = a^b;...b {^b;#b}
- a^1,e1;b = a^b,e;...b {^b,e;#b}
Continue to apply this kind of multiple substitution in the definition
of subscripted arrow and star operations.
It is clear that the operator counter c
and the following operator subscripts
d,e,..
are similar uploadable iterators
(with the provision that arrows ^R..
do not allow series of
mixed subscripts
but stars *R..
do).
We will suffix c
before
the row of arrow coefficients R
to improve readability.
Then to retrieve the original form with countable operators, you should substitute
a^R;..b
{^R;#c} for
a^c,R;b
in this general formula for
subscripted majority arrows.
- a^1;b1 = a^0;(a^1;b) == a^0;... {a#b1} = a... {a#b1 0^}
- a^1,...;b {1#k1} = a^b,...;b {b#k}
- a^1,...,n1,R;b {1#+k} = a^b,...,n,R;b {b#k}
- a^c1,R;b1 = a^c,R;(a^c1,R;b) == a^c,R;... {a#b1}
With uploading we substitute higher parameters
for a value accumulated in a lower parameter – that is b
in case of subscripted arrows and stars. Without this mechanism
it's hard to see how ordinary unnested functions can move past the
Ackermann-Conway
class as represented by chained arrows.
Uploading parameter values from the first row
is definitely the way forward to conquer the next
dimension.
# Piecemeal defined uploading
Functions defined by simultaneous substitution in the first row
can also be represented by recursion with single substitutions.
Having an earlier parameter (value b
)
uploaded parameters ahead (substituting for d
)
can just as well be covered by substitution to the next parameter
(b
for c
and
c
for d
).
For example, in the evaluation of a^1,e;b
you can opt to substitute b
for c=1
and in the next step c
for d=1.
The net effect of this definitional detour would be a double
upward substitution as usual, but when you count down e
the parameter dependent on it is substituted at value
d=2 instead of d=1.
Take a step forward
to find our upload axiom for single
^R
composed of a series of separate substitutions
as every parameter is counted down to initial value 0
(instead of 1
).
== a^b,..,0,z1;b {b#k} = a^b,..,z;b {b#k1}
But we have grave doubts about the approach above.
Zeros are superfluous characters and strange iterators
(though this procedure may well be used to define them).
More importantly, the same rules do not work for subscripted
*d,e;
minority stars.
Now we take another, perhaps more natural direction.
== a^1,b1,b,..,z;b {b#k-} = a^b,..,z;b {b#k1}
This illustrates upload by series of single substitutions from the right.
Only the partial rule for parameter c=1 must be different from
that of the parameters to its right,
which temporarily get 1
extra.
Later, when we'll insert a new rule in bigI
to accommodate
mixed star
subscripts, you'll see that the capacity lost by bigI's
iterator collapse
is redeployed to lift it a level higher in bigI's
first row
with waitor.
So if chained arrows send forth a whole
row
of similar iterator y
destructions,
this dormant capacity in the keeping might just be the thing
that gracefully lifts a function of mixed arrows
up to a higher heaven.