Today we will shoot arrows to the northwest, with the lights of Big numbers shining on the horizon.
Superchained →↑^{..}
arrows
§3.3
Continuing from the three recursive algorithms
of multiplication, Knuth's up-arrows and Conway's chained arrows,
we combine the right →
and up ↑
arrow signs
to construct a bigger system of superchained arrows.
We build a maximal function, under the restriction that
the evaluation of variables runs one way
(from right to left, that is, without Bowers' uploads).
In this chapter we extend Knuth-Conway^{ }
with the new rules E.6
and E.7
,^{ }
that reduce multiple right-up
→↑^{..}
arrows.
Superchains of right-up arrows are a way of expanding^{ }
chained arrows to multiple dimensions.^{ }
Later come the supermixed
→↑^{..}..
operators and their extension with ↓
and ←
indicators
(arrow index level separators).
Generic arrow notation is used for^{ }
↑ → ↓ ←
mixed and indexed arrow types.^{ }
- All arrow operations are evaluated from right to left (no precedence).
- Generic arrow sign
†
(dagger) holds a single (mixed-indexed) arrow. - Arrow string
‡
(Dagger)†_{i}.. {:n>0}
is greedy for more arrows. - To distinguish arrow wildcards we use quotes
‡’
‡”
or subscripts.
We will revive features of up-top system
B.
to extend chained arrows
to a superarrow system E.
,
so that rule B.3
inspires E.6
and rule B.4
inspires E.7
.
Rule E.6
copy-paste-repeats the
superarrow y‡
"variable plus operator". This can be inserted either step by step
or by direct substitution from ↑y→z
end
to x→y
end form.
So that rule E.7
,
an instance of which copy-pastes the "variable plus operator" once,
can be overlooked in the direct reduction train
E.6.1.7
, which eventually returns
all superchained dimensions to the row of chained arrows.
The other rules (the E.4.5
nesting train to E.3
)
that copy-paste-repeat the superchained
X‡
"word plus operator"
are supplanted from list D.
in last chapter.
For the purpose of comparison the nested version of rule
E.4.
shaped after list
C.
is often preferable.
- let ‡_{=} → _{or} ↑^{..} _{or} →↑^{..} {↑:k>0}
- E.1 > D.1 Y1‡1 = Y1
- let / _{=} W1* _{or} W1↑^{..} {w} _{or} 0
- E.2 = D.2 /y→z1 = /y*y→z == /.y*..y→1 {:z} _{E.1}= /.y*..y {:z} =_{*.}= /y^(z+1)
- E.3 = D.3 Y1↑z = Y1→z
- let X _{=} /X’ X’_{=} 1T1↑^{..} {1↑∉1T ↑:k≥0} X”_{=} X’ {k=0} _{=} 1T1 {1↑∉1T} _{ } _{=} t_{i}→↑^{..}..t_{n1} {m_{i}≥0 :n≥0}
- E.4 ~ D.4 X→y→z1 = X↑^{..}y {z1} ≈ C.4 ≡ /X”→(X”→y-→z1)→z {y>1} E.5 ≡≡ /X”→(..X”→1→z1.)→z {:y-:} ≈ C.3 _{E.1}≡ /X”→(..X”.)→z {:y-: y≥1}
- E.5 ~ D.5 /X’↑↑y1 = /X’↑X’↑↑y == /.X’↑..↑1 {:y1} _{E.1}= /.X’↑..X’ {:y}
- E.6 W†x‡↑y→z1 {W†?} where ‡_{=}→↑^{..} {k≥0} = W†x‡x‡↑y→z == W†.x‡..↑y→1 {:z1} _{E.1}= W†.x‡..↑y {:z1} _{E.7}= W†.x‡..x→y {:z1}
- E.7 W†x‡↑y1 {W†?} with ‡_{=}→↑^{..} {k≥0} = W†x‡x→y1
The outer drop of
‡1
in rule E.1
also takes care of rule C.3
with its penultimate y=1
elimination.
In this regard it seems auspicious that (this initial) step by step
reduction of chained arrows gets no mention in Conway's book.
We can improve this to a right elimination shortcut
for chained and superchained arrows,
and then extend it to all mixed (not indexed!) arrows.
- X1→1‡Z1 = X1→1 = X1 (shortcut
E:8
for superchained arrows) - X‡→1‡’Z1 = X (shortcut
for mixed arrows)
Watch chained arrows being built up by the
→↑
operation from the 2nd to the 1st row
(also check the
example
3→↑3→2
we worked out in last chapter).
- a→↑b _{E.7}= a→a→b _{E.4}= a↑^{..}a {:b}
- a→↑b→2 _{E.6}= a→a→↑b→1 _{E.1.6}= a→a→a→b
- a→↑b→c _{E.6}= a→..b {:c1}
- a→↑b→2→2 _{E.4}= a→↑b↑↑2 ≡ a→↑b→(a→↑b→1→2)→1 _{E.5.1}= a→↑b↑a→↑b ≡ a→↑b→(a→↑b) _{E.7.7}= a→..a→b {:a→a→b}
- a→↑b→c1→d1 _{E.4}= a→↑b↑^{..}c1 {d1} ≡ a→↑b→(a→↑b→c→d1)→d _{E.5.1}= a→↑b↑^{..}..a→↑b {d :c} ≡ a→↑b→(..a→a→b.)→d {:c:}
Superchained arrows may look like operators,
but their actual function is to separate array dimensions.
Just like single right arrows →
separate variable places, the →↑
operator-separator sets rows apart, next come →↑↑
in between plane arrays, next
→↑↑↑
in between cubic arrays, etc.
By appending multiple →↑{m}
up arrows
we expand the linear arrays of chained arrows
to a type of structure that Bird calls
multi-dimensional arrays.
But here we resolve expressions consequently from right to left,
which is systemically slower.
However we can conjecture, that over the same structures,
an arrow algorithm resolving from the right end will always trail
one recursive rule level behind a similar array system
dominated by upload rules?¡
Check your compass!¿
Alternative superchains §3.4
Have a closer look at the system E.
definition. Test drive some alternatives.
Rule E.7
is a fine embellishment,
which would become^{ } superfluous,
were we to write a new rule Eº3
of^{ } X‡z
= X→z
^{ } with
‡_{=}→↑^{..}
as an option, added to ‡_{=}↑
above.^{ }
Then Eº6
as
E.6.1º3
would evaluate^{ }
x‡↑y→z1
= x‡..x→y {:z}
quite decently.^{ }
Such a system Eº
is one rule simpler!
The main reason^{ }
for not implementing it, is that we find mighty operations
x→↑^{..}y
without meaning ugly.^{ }
The superchain rule E.6
is very fast,
while E.7
achieves little with
its first-final entry.
Consider a quick and dirty system F.
which depends on brackets.
Compared to rule E.7
the nested superchains of F.4
gain one parameter countdown at the start of each row.
- F.1 > C.1 X‡1 = X
- F.2 = C.2 W*y→z1 {W*?} = W*y*y→z == W*y*..y {:z}
- F.3 ~ C.3 X‡1→z = X
- F.4 ~ C.4 X‡y1→z1 = X‡(X‡y→z1)→z == X‡(..X.)→z {:y:}
- F.5 > A.3 W†y‡↑z1 {W†?} = W†y‡y‡↑z == W†.y‡..y {:z}
Right-up arrow rule F.5
repeats its preceding operators the same way as the up-arrow
rule A.3
did before.
The nesting mechanism of rule F.4
is exactly that of C.4
chained arrows.
So this algorithm is a natural continuation
of Knuth and Conway's.
Our system E.
is rather complex,
it contains 2 more rules (or 3 extra if rule E.4
is to increment its up arrows step by step by
D.4a.b
).
And its action is hampered, where E.7
seems to squander first entries on every row
(remember Rózsa Péter achieved double recursion
with two parameters, us depleting the first entry is business as usual).
Still with E.
we manage to run a natural algorithm without any brackets,
which gains a character type (or two). And the loss of a single parameter
does not significantly slow down function speed, because rule
E.6
dominates the expansion of row sizes.
- E. a→↑↑a→b1 _{E.6}= a→↑..a→↑a→a {:b} _{E.6}= a→↑..a→..1 {:b a→:a2} ~>
- F. a→↑↑b2 _{F.5}= a→↑..a→↑a {:b} _{F.5}= a→↑..a→..1 {:b a→:a} ~
- Eº. a→↑↑a→b2 _{Eº6}= a→↑..a→↑a→a {:b} _{Eº6}= a→↑..a→..1 {:b a→:a1}
Can you tell if system F.
past the 1st entry keeps running exactly concurrent with the simplified system
Eº
(defined as an example) above?
Then the difference between systems
F-E
is always just less than an entry, amounting to 1
on the next row, where it is wholly absorbed.
As in example E,
where the comma indicates that any string
W‡
can be prefixed to following expressions.
- E, a→↑a→b _{E.6}= a→..1 {:b2} == a→a→x_{E} ~>
- F, a→↑b _{F.5}= a→..1 {:b} == x_{F} ~
- Eº, a→↑a→b _{Eº6}= a→..1 {:b1} == a→x_{F}
Imagine a system F'
that applies (the E.5
principle of)
word repetition limited by right-up arrows in a new wider rule
F'5
over the row.
Or another system F"
with an even wider word redoubling
rule F"5
limited by equal-or-larger right-up arrows.
These would not be significantly faster,
because in F.
we can use
2^z
instead of
z+1
to approximate its results,
and for big enough
z~2^z
is about equal.
- let Y _{=} y→..y {:n-≥0}
- F'. Y→↑z1 =_{F'5}= Y→Y→↑z = Y→Y→Y→Y→↑z- == Y→..1 {:2^z} = y→..1 {:n*2^z}
- = F. y→↑(2↑z) {n=1} =_{F.5}= y→..1 {:2^z}
- < F. y→y→↑(2↑z1) {n=2} =_{F.5}= y→..1 {:1+2*2^z}
- < F. y→..↑(2↑zm) {:n=2^m} =_{F.5}= y→..1 {:n-1+n*2^z}
To investigate this argument we study a similar algorithm
at an earlier stage: a string redoubling rule (worse case).
Its heart operators ♥{c}
fit in with the Grzegorczyk hierarchy
as the resulting numbers converge to normal superpowers.
- ♥.1 X♥ = X ♥.2 X♥{c}b = X♥{c-}X♥{c}b- == X♥{c-}.. {:2^b}
- a♥1 = aa♥ = aa = a*2 a♥2 = aa♥1 = aaaa = a*4 a♥b = aa♥b- = a.. {2^b} = a*2^b
- a♥♥1 = a♥a♥♥ = a♥a = a*2^a a♥♥2 = a♥a♥♥1 = a♥a♥a♥a ~ 2^2^(a*2^a) ~ 2^^3\^a a♥♥b = a♥a♥♥b- = a♥.. {:2^b} ~ 2^^(2^b)\^a
- a♥♥♥1 = a♥♥a♥♥♥ = a♥♥a ~ 2^^(2^a) a♥♥♥2 = a♥♥a♥♥a♥♥a ~ 2^^2^^2^^(2^a) = 2^^^4\^a a♥♥♥b = a♥♥.. {:2^b} ~ 2^^^(2^b)\^a
- a♥{c}b ~ 2^^{..}(2^b)\^a {c} ≈ a^^{..}b {c}
The further advanced the position in the algorithm the less
impact a word repetition F'
or even a word redoubling F"
is expected to have.
Here we let E.4.5
nest superchained words and E.6
increment superchain dimension sizes.
Together with style C.
(bracketed)
nesting equivalences, this welds system E.
into a practical comparison tool,
on a par with the first row of Bowers' Beaf.
The alternative systems in this chapter
run parallel to the superchains of E.
which is our system of choice.
Though any of these systems will compare as equal against the row in
Beaf (which is dominated by the upload
of accumulated values from left to right).
Compare the structures of E.
arrows with
Bowers' arrays
to match function speed.
- From the start to
a→b→c
equals the 3 entries{a,b,c}
in Beaf. - Chained row
a→↑b1→c
comes after 4 entries{a,a,b,c}
in Beaf. - Superarrows plane
a1→↑↑b→c
after 5 entries{a,a,a,b,c}
Beaf. - Multidimensional
a→↑^{..}a {b}
before a row{a,b2,[1]2}
of Beaf.
This leads us to the conclusion, that both the expansion
of chained arrows to multiple dimensions in system
E.
and Bowers' repetitive upload rule
over the first row, count as 4th recursive algorithms.
And that every next entry in Beaf covers a higher dimension
of superchained arrows,
with the entry's value counting the dimension's size.
That way, the row structure of Beaf
stays one recursive level ahead of chained arrows.
No comments:
Post a Comment