Today is selling archery gear to the Maya gods at a discount. We create a natural extension of Knuth-Conway style arrows, for comparison against various array functions for Big numbers.
Knuth's up ↑.. arrows
§3.1
There are two popular types of arrows available
for the definition of Big numbers.
In this chapter we use the countable up-arrow
↑
as operators for superpowers.
Next chapter we study the right-arrow →
parameter separator for the row of Conway's chained arrows.
All our arrow structures are painted blue
and resolved from right to left (right associatively).
We prefer to speed up multiplication
(the first recursion of repeated addition)
by substituting a*b = a.. {b}
directly into an expression.
Applied as in rule *. below
which goes straight to the result.
To start more rigorously we can define addition as the shifting of
1 between variables,
and multiplication by repeated addition of the same number.
Though Karatsuba multiplication for large numbers is the faster algorithm,
we like to keep it simple.
Adding step by step while avoiding brackets is achieved with the plus
+ sign in between operands.
- *.0 X+a1 = X1+a == Xa+1 = Xa1
- *,1 a*1 = a
- *,2 a*b1 = a+a*b = a(a*b) == a+..a*1 {:b} = a..(a*1) {b} = a+..a {:b} = a.. {b1}
We use
RepExp
notation in the definition of rules
to repeat substrings in the expression.
A wildcard X stands for an arbitrary substring
(which honours the context),
and X may be void of characters.
But parameters are never empty,
and our variables p
are greedy for number signs (eat all 1..).
So that rules that start on a variable
(above rule *,2
and rules A, below)
can be thought to have an inactive (possibly empty) left part
X with an operator sign on the right end
(not ending on 1 or ω etc.).
- *. X†y*z {X†?} = X†y.. {z}
A virtual left part X
is indicated by a comma ,
instead of a dot . in the rule number.
To make this optional X explicit we let it
follow by a question mark {X?} in the repertory.
The dagger character †
is a generic operator sign, for instance * number repetition.
Follows the rule list for the evaluation of ↑..
operations (in the active right part of an expression)
in the context of up-arrows.
Knuth counted his arrows up from the initial A,2
power and so on == by direct substitution,
but we prefer a stepwise = approach.
- A,1 a↑..1 {c} = a => a↑1 = a
- A,2 a↑b1 = a*a↑b == a*..a↑1 {:b} = a*..a {:b}
- A,3 a↑..b1 {c1} = a↑..a↑..b {c c1} == a↑....a {c :b}
The superpowers ↑..{c≥2}
expressible now are already far greater
than any realistic quantity you can ever hope to imagine.
The fantastic world record number, the unspeakable tetration
10^^(10^(5*2^120)) from Buddhist scripture,
is smaller than 4↑↑↑3
its neighbour pentation.
Because the counter starts c=1
at a power (not multiplication),
we have a nice shortcut.
- 1*1=1 => X↑1↑..z {↑:c>0} = X↑1 = X
At chained arrows rule C.3
we get the same total right drop at the penultimate operator.
So we'd like to see this feature return as a consequence
of other arrow systems. But in the extended system
B. below, we can only drop the
t→ is
1→ from in between.
Backslashed operations on top of up-arrows are helpful
to compare the growth of various functions in the range of superpowers
(to assess the Grzegorczyk hierarchy).
A simpler extension with one right arrow on top fulfils a similar purpose
(and heralds the continuation of chained arrows to higher dimensions).
This refined up-top system B.
is defined here, and illustrated by expressions with the old
\^ backslashes.
- B,1 a‡1 = a where ‡=↑.. {k>0} or ‡=→
- B,2 a↑b1 = a*a↑b == a*..a {:b} = a^(b+1)
- B,3 a↑..t→b1 {c} = a↑..a↑..t→b {c c} == a↑....t→1 {c :b1} = a↑....t {c :b1} = a^..(b+1)\^..t {c+1 c}
- B,4 a↑..b1 {c1} = a↑..a→b {c} = a^..b\^..a {c+1 c}
Multiplication *
is the first recursive rule,
which repeats the addition of a number.
The series of up-arrows ↑..
repeat earlier operations of repetition.
First come the a↑b powers,
next the power towers a↑a↑t up until
a↑..t {:b}
which equals a↑t→b
and in turn a↑a→b
equals a↑↑b1 tetration.
Then generalize this process to superpowers expressed by multiple
a↑..b {:c}
arrows, in total a double recursion.
Superpowers have no counterpart in physical reality –
their numbers are just too big to be of practical use.
Consider the size of
3↑↑4
evaluated both in the system A.
of up-arrows and in the extended system B.
for example.
- 3↑↑4 A.3= 3↑3↑↑3 = 3↑3↑3↑↑2 = 3↑3↑3↑3↑↑1 A.1= 3↑3↑3↑3 A.2= 3↑3↑3*3↑2 = 3↑3↑3*3*3↑1 A.1= 3↑3↑3*3*3 *.= 3↑3↑27 == 3↑7625597484987 ~ 1E3638334640024
- 3↑↑4 B.4= 3↑3→3 B.3= 3↑3↑3→2 = 3↑3↑3↑3→1 B.1= 3↑3↑3↑3 B.2= 3↑3↑3*3*3 *.= 3↑3↑27 ~ 1511 GB
Though this tetration still fits on a
2 TB harddisk,
larger superpowers can't be digitalised
or written physically in number base.
All of our 1E120 bit of
quantum-information space fails to store
4↑↑4 in binary.
Working out the recipe would run the cosmos to ruin.
Conway's chained → arrows
§3.2
In 1996 John H. Conway published his chained arrow notation
in “The Book of Numbers”.
We think his arrow operators →
should become the benchmark of choice
to further classify functions in the fast-growing hierarchy.
Define a self-sufficient list of rules for Conway's chained arrows.
- C.1 X→1 = X
- C.2 a→b1 = a*a→b = a↑b1 == a*..a→1 {:b} = a*..a {:b}
- C.3 X→1→z = X <=> X→1→Z = X
- C.4 X→y1→z1 = X→(X→y→z1)→z == X→(..X→1→z1.)→z {:y:} = X→(..X.)→z {:y:}
Conway directly substituted the three entries
a→b→c
= a↑..b {c}
but we can reduce the three chained arrow entries to multiple up-arrows
step by step.
This proves that the system C.
can express every superpower
and reduce it to multiplications.
- a→b1→1 = a→b1 = a↑b1
- a→b1→2 = a→(a→b→2) = a↑(a→b→2) == a↑..(a→1→2) {:b} = a↑..a {:b} = a↑↑b1
- a→b1→3 = a→(a→b→3)→2 = a↑↑(a→b→3) == a↑↑..a {:b} = a↑↑↑b1
- a→b1→c1 = a↑..(a→b→c1) {c} == a↑..b1 {c1}
The main rule C.4 in Conway's system
relies on bracket characters to nest expressions.
Now we transform it to a chained-up arrow system D.
where brackets are not required, because in
X→y→z the operations starting on
↑ take over as word delimiters.
In this context we allow
multiple up ↑..
and single → right arrows,
with temporary up-right arrows
↑..→ {z>0}
as auxiliary constructs for stepwise operator change.
In wildcards all contextual signs are valid, so in
X↑
the X may end
on ↑.. arrows.
Parts of a rule that are painted grey
remain unchanged in its evaluation.
A part denoted by a question mark
{X?} may be lacking
(if void the expression still matches the rule).
To demand that string X is part of Y
we write X∈Y, and
not to allow X to match in Y
we write X∉Y,
in the Rep (repertory) for the Exp (expression).
Our rigorous list of rules for alternative chained-up arrow algorithm
D.
It expands the up-arrow context of system
A,
but is incompatible with system B, up-top.
(Can you make it compatible by adapting rules
D.2.3?)
- D.1 X1‡1 = X1 where ‡=↑.. {k>0} or ‡=→
- D.2 W†x→y1 {†=↑or* W†?} = W†x*x→y == W†.x*..x {:y}
- D.3 X1↑y = X1→y
- D.4a X→y→z1 = X↑→y→z == X↑..→y→1 {z} .4b = X↑..→y {z} = X↑..y {z1}
- D.5 W↑1X↑↑y1 {W↑? ↑1∉X} = W↑1X↑1X↑↑y == W↑.1X↑..1X {:y}
Rule D.3 handles both the referral of
x↑y↑z powers
to rule D.2
and the removal of (virtual) brackets from
x→y↑z chained arrows.
Rule D.4 can be done
step by step
(strictly a dual rule),
or substituted straight away in grand Conway style.
Rule D.5 reduces
↑..
{c1≤z1}
up-arrows by repetition of 1X chains
pi→..pn1↑..
{:n c}
where 1X is delimited by (but not contains)
lone ↑.. up-arrows.
This clause of matching the repeated string 1X
from the right
down to (the left end or) ↑1
(or generally until q↑‡p
is met)
replaces the nesting brackets of rule
C.4.
Take rule D.4 and D.5
together to meet the conclusion of Conway's original system.
- X→y1→z1 D.4= X↑..y1 {z1} D.5= X↑..X↑..y {z z1} C.4≡ X→(X→y→z1)→z =D.5= X↑....X↑..1 {z :y z1} C.4≡ X→(..X→1→z1.)→z {:y:} D.1= X↑....X {z :y} C.3≡ X→(..X.)→z {:y:}
From this format it is clear that chained arrows repeat
the double recursion of up-arrows,
taking two entries from the end of the row.
By rule D.3 the result is appended
to the row again as a new chained entry,
so each double recursion consumes a single entry.
Then over the length of the row we count the
3d recursive algorithm.
We'll reduce two chained arrows expressions
3→4→2 (the
example
3↑↑4 in last chapter)
and 3→3→3→3
(introducing the →↑↑ row creator),
so you can see the rules at work.
- 3→4→2 D.4= 3↑→4→1 = 3↑→4 = 3↑↑4 D.5= 3↑3↑↑3 = 3↑3↑3↑↑2 = 3↑3↑3↑3↑↑1 D.1= 3↑3↑3↑3 D.3= 3↑3↑3→3 =D.2= 3↑3↑3*3*3 =*.= 3↑3↑27 =D.3.2.*.= 3*..3 {:7625597484986}
- 3→↑↑2 E.7= 3→↑3→2 E.6= 3→3→↑3→1 E.1= 3→3→↑3 E.7= 3→3→3→3 = 3→3↑→3→2 = 3→3↑↑→3→1 = 3→3↑↑→3 D.4= 3→3↑↑↑3 C.4= 3→3→(3→3→2→3)→2 D.5≡ 3→3↑↑3→3↑↑↑2 C.4= 3→3→(3→3→(3→3→1→3)→2)→2 D.5≡ 3→3↑↑3→3↑↑3→3↑↑↑1 C.3= 3→3→(3→3→(3→3)→2)→2 D.1≡ 3→3↑↑3→3↑↑3→3 C.2.*.= 3→3→(3→3→27→2)→2 D.2≡ 3→3↑↑3→3↑↑3*3*3
- a→b→c1→2 ≡ a→b↑↑c1 a→b→(a→b→c→2)→1 ≡ a→b↑a→b↑↑c a→b→(a→b→c→2) ≡ a→b→(a→b↑↑c) a→b→(..a→b→1→2.) {:c:} ≡ a→b↑..↑1 {:c1} a→b→(..a→b.) {:c:} ≡ a→b↑..a→b {:c}
- #Garham = 3→3→(..4.) {:64:} < 3→3→65→2
Watch the tetration
3↑3↑3↑3
being reduced to mere trillions of multiplications.
Compare the chained arrows
3→3→3→3
which is even larger than Gardner's Graham's number.
And this is hardly where it all ends… Long after the sky has fallen down a tiny typist will travel the universe of Big numbers on the back of an arrow.
