Big Arrows Compass I

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.