Alexa 2nd - Fluid Structures

11:24 AM

Today the Alexa radix system for big numbers will be nested to great depth.
We extend the first row defined in last blog to multiple dimensions and then to nested arrays.

§3. Nested arrays

In all arrays the position of an entry, specified by its left separator, determines the function or power of its value.
We can start with the comma , or [1] in row space, and either go on to count a series of commas (row format), or index positions directly in a subarray (sentry format).

In the common row format same separators (seps) always occur, as they are expanded in series, increasing in power towards the right.
In sentry format expressions can be evaluated completely without repetition of seps. Here a pair of an indexed sep and number entry is called a sentry. Duplicate seps in the input are allowed, but this could be expressed with unique seps instead.

Any array function can be written either with sentries or rows, but the Alexa sentry format behaves as a fluid. In a fluid system the sentries can be moved about inside their parent array without changing the result.
There are no rows or dimensions there, just sets of sentries, as sentries can freely hop over each other, in series or alone. The only restrictions on the movement of fluid sentries are: not to leak from their parent brackets or to seep into some subarray.

Fluid radix system Alexa can have her sentries roam freely, because she persistently uploads the constant a.
Solid systems like Blixa upload the variable b, which is fast growing, and those array entries have to be rigidly kept in order.
There is no need for unique seps [p,X] in a solid system, so usually that number p to count subarrays [X] is represented by positions in the parent space.

The rules defined for linear Alexa in the last blog cover all nested arrays as well.
In a fluid evaluation rules can be applied in any order. Sentries [X]n can be reduced individually and the resulting numbers added up on the left, while the parent array is evaluated at the same time.
However, to preserve the radix character of Alexa, where no entry becomes larger than a=10, we should evaluate expressions consistently from left to right.

§3.1. Sentry to row format

In sentry format each array in Alexa holds a fluid set of sentries: sep & entry pairs that may float about during an evaluation.
We can translate this to row format: a solid structure for multiple seps of the same type. One nested row contains the information of two levels of nested senties.
Vice versa we can translate the array functions of Bird to a format where all substructures are unique. This just doubles the number of nested levels.

[1]n = ,[]n = ,n      [1]m[2]n = ,m,n
[n]1 = ,{n}1      [,1]n = ,[1]n
[1,1]n = ,[1],n     [n,1]1 = ,[1],{n}1
[,2]n = ,[1],[1]n      [,n]1 = ,[1]..1 :n
[[2]1]n = ,[2]n     [n[2]1]1 = ,[2],{n}1
[m,n[2]1]1 = ,[2].,[1]..,..1 :n :m
[[2]n]1 = ,[2]..1 :n     [[n]1]1 = ,[n]1
[[,1]1]n = ,[,1]n     [[,1]n]1 = ,[,1]..1 :n
[[n,1]1]1 = ,[n,1]1     [[,n]1]1 = ,[,n]1
[[[2]n]1]1 = ,[,,n]1     [[[n]1]1]1 = ,[,{n}1]1
[..n..]1 :kk: = ,[..n..]1 :k:
[..n..]1 :kk1: = ,[..,{n}1..]1 :k:

Differences between the sentry format on the left, and the row format on the right:

• In row format we prefix a separator comma to all subarrays.
• A plain comma equals sep [1] in sentry format, but sep ,[] within rows.
• Nested subarrays [X] on the row are matched with seps on even sentry levels. Their repetitions on the row can be matched with seps on odd sentry levels, which are coloured green for contrast.

Other googologists count their entries down to 1, not to void, like we do here. But they leave the room to combine separators [X][Y] unused in their algorithms.
Recursion theorists often put new and faster entries on the left: in reverse direction.
You can choose the notation styles you like for your own projects, but we find our sentry format is natural for nested arrays, because the number output figures.

§3.2. Nested Alexa

Calculate some basic nested arrays in Alexa. Apply her rules for the linear system, styled in sentry format.

[1]p = ,p = a,p- = aa,p-- = a*p
[2]p = ,a[2]p- = a*a[2]p- = a^2*p
[p]1 = [p-]a = a^p-*a = a^p
[[1]1]p = [,1]p = [a]p = a^a*p

[1,1]p = [,1]a[1,1]p- = a^a1[1,1]p- = a^a1*p
[2,1]p = a^a2[2,1]p- = a^a2*p
[p,1]1 = [p-,1]a = a^ap
[,2]p = [a,1]p = a^aa*p
[,p]1 = a^(a*p) 

[[2]1]p = [,a]p = a^a^2*p
[1[2]1]p = [[2]1]a[1[2]1]p- = a^(a^2+1)*p
[p[2]1]1 = [p-[2]1]a = a^(a^2+p)
[,p[2]1]1 = [a,p-[2]1]1 = a^(a^2+a*p)
[[2]p]1 = [,a[2]p-]1 = a^(a^2*p)
[[p]1]1 = [[p-]a]1 = a^a^p 

[[,1]1]p = [[a]1]p = a^^3*p
[[,1]p]1 = [[a]p]1 = a^^3^p
[[1,1]p]1 = [[,1]a[1,1]p-]1 = a^(a^a1*p)
[[p,1]1]1 = [[p-,1]a]1 = a^a^ap
[[,p]1]1 = [[a,p-]1]1 = a^^3+*p
[[[2]p]1]1 = a^^3+*a*p
[[[p]1]1]1 = a^^3+^p 

In Alexa the next nested array expresses the next power on top of a power tower. This follows easily from recursion over [S]1 = a^S where the subarray S can be independently reduced to number.

[..S..]p :n: = p*a^^n+^S

Depth of nesting in Alexa translates to the tetration ^^ exponent n which dominates these functions, against shallower subarrays S.
The radix aspect of Alexa lifting a digit length p to a power a^p has lost importance. To remove the linear top or drop the bottom nest decreases depth n by just 1.

To classify his linear array space Bird counted it as ω. He notated his arrays in row format and nested them to ω depth. In the previous section we saw that row format with its multiple seps takes half the nested levels of our sentry format with unique seps. Here ω^^ω = ε0 so Bird's nested arrays count up to class ω^^ωω = ω^^ω+^ε0 = ε1.

After rows come planes and then cubes, etcetera, who is to say what format is the natural? It's our result of tetration here, that suggests that unique separators between entries are elemental. We choose the sentry format for all our array functions.

Alexa 1st - Radix Structures

10:21 AM

This first article designs the system Alexa to create big numbers and explore functions like: tetration, Knuth's and Conway's arrows, Bowers' exploding array function and Chris Bird's beyonds…

The images show deconstructivist artworks by Alexa Meyerman, in dedication.

Life is short, Alexa is long.

§1. Construction plan

Structurally Alexa is an array of number variables, which are separated by subarrays.
These subarrays will be delimited by various types of brackets as the system becomes more advanced.
The algorithm applies a list of rules to evaluate sound expressions step by step.

Structure + rules = system.

Function rules manipulate the expression as a whole, but this can become overly complex.
Rewrite rules that search → for a place to insert a term (like a machine flowchart) are clearer and get the work done just as well.
In calculations we often perform a combination of such rules in one go.

Small word in, large word out, the expressed number just changes shape.

Proper input for the Alexa system is a radix expression, with digits smaller than radix a in each entry. These radix expressions form a set of unique numbers.
When we evaluate the input, by rule of Alexa many intermediary expressions are formed. In the throughput, the total at base b grows larger, while new entries are loaded with radix a.
Finally all structure is lost and a plain number is output.

The Alexa radix system past the first row extends your common number systems.
Though separator types can be advanced, their effect on the growth rate remains relatively slow, which makes Alexa suited as a benchmark function.
With a single change of her rules: instead of constant a to upload the variable total b, we create a faster class algorithm named Blixa, after Blixa Bargeld (founder of Einstürzende Neubauten). His function grows explosively when nested, and will overtake the arrays of Bird-I-IV beyond, as soon as optimal structures are put in place ;-)

§1.1. Number toolkit

Make decimal digits 1,2,3,4,... count 1,11,111,1111,... series of ones. Consider that all natural numbers n consist of 1{n} units one.
Decimal numbers like 2^^5 = 2^65536 ≈ 2E19728 ≈ 1E2E4 with estimates in multiple E notation (nEp = n*10^p) are in brown font.
Raise some early powers with the help of Wolfram Alpha.

Zero is   void, so the sign 0 denotes an empty variable.
We put a minus sign - on the right of a number to decrement it, so 4- = 3.
All variables a to z are natural numbers ≥0 here. Capitals F G H are reserved for functions. Wildcards M to Z stand for subexpressions, words that may be empty, with the requirement for M to W that inside brackets are matched (subarrays are closed).

Select a term T.. or X.T..Z with the dots, to repeat it :r times (the rep).
If a variable i or j is repeated, it will increment from 1 to r on the right.
Another tool for rewriting is double rep :n: repeating a term .X.. from left to right and a term ..Y. from right to left, simultaneously on the two dots.
Example to nest arrays by double rep: a.[..]1 :4: = a[[[[]1]1]1]1.

The elementary operators are + * ^ where plus + in equations postpones addition. Naturally when quantities ab = ba are joined, they are directly added.
Multiplication can be expressed a*b = a{b} = a.. :b by operator, quantifier or as repetition of addition. Exponentiation or powers by majority caret a^b = a**b or minority stars, where (more) carets have precedence over (less) stars.

§1.2. Superpower stars

Donald Knuth extended the power operation to superpowers ↑.. by Knuth's up-arrows. Of this countable operator sign ^.. usually just the arrowhead or caret remains.
Starting from addition of 1 all these operations can be constructed by primitive recursion, from the elementary (addition, multiplication and exponentiation) up to superpowers.

a^..b ^:c1 = a*{c2}b

As superpower operators we prefer minority stars a*{c}b because they can start by counting *{0} zero, which results in natural ab addition.
Two new rules are enough to express all primitive recursive functions.

• *0 a*{0}b = ab (add)
• *1 a*{c1}1 = a (identity)
• *2 a*{c1}b1 = a*{c}(a*{c1}b) (step) or = a*{c1}b+*{c}a =2:1.= a*{c}..a :b

Operators are resolved in order ^.. ^^ ^ * ** *.. + of precedence, or else, if adjacent operations are equal, worked away from the right.
Our postponed operators +*{c} and +^{k1} must wait on top. We use them to build operator towers from fast algorithms, for the tricky steps in between.

2^^^3 = 2^^2+^^2 = 2^^1+^^2^^2 = 2^^4
      = 2^^3+^2 = 2^^2+^2^2 = 2+^2^4 = 2^16 = 65536

After the superpower *{c1} has raised its *{c} tower in full, we let drop the plus + from the pop-stars to put their star operation on top. Then the part to the right of a postponed operation can be evaluated on the fly.

§1.3. Base entry

In our new Alexa system for a matrix [M] of variables in structures, we leave radix a outside on the left. But often we show just the array M and insert constant a by rule.

Equivalence = of function type evaluates the matrix as a whole, but by rewriting we can change terms locally in the expression. When a rewrite rule has to be applied strictly from left to right in the expression we specify this with => an arrow.
Core rewrite rules are orange coloured. We derive the fuchsia methods from these.
Function rules for whole expressions are green. To change format use a blue mark.
Formats are makeshift notations, but expressions obviously stay ≡ equivalent.

• 0.0 Alex:a[M] ≡ M (format)
• 1.0 Alex:a[b] = b (output)

At the final evaluation, rule 1. sends the number left in the base entry b to the output.

The output number will be a series of units u..n :r of size r. Below we work with natural numbers 1.. from unit 1, but any infinity can be substituted for radix a too.

11:29 AM

§2. Linear array

After the basic setup Alexa has four rules to reduce linear arrays that can be nested.

• 2.0 [b_[] = [b (void)
• 3.0 _[S]] = ] (end)
• 4.0 _[S][ = _[ (clear)
• 5.0 _[1S]1 = _[S]a_[1S] (load)

A linear array has a single row of entries.
On Alexa's first row each entry p is placed right of a uniquely indexed [n] separator. We call the separator-entry pairs [S]p sentries.
Separator arrays [S] can be expanded to deep nested arrays, and in Alexa her linear rules work there too. Nested arrays are treated in the next blog.

Load rule 5. works, because empty seps [] dissolve 2. at the array base. Then the total b naturally increases by value a. To apply rule 2. in a subarray let b=0 always be empty.

Combining rules 5. & 2. with commutativity ba=ab creates our rule ab. of addition. Which by repetition yields a*c+b multiplication. Note that in Alexa addition not only takes place at the main level, but also at the base index of subarrays.

• ab. [b_[1]1Z 5.= [b_[]a_[1]Z 2.= [ba_[1]Z = [ab_[1]Z (add)
• [b_[1]cZ =ab.= [a{c}b_[1]Z (multiply)

For multiplication a*c as such, put b=0 and let Z equal the ] closing bracket of the main array. Apply addition rule ab. repeatedly, clear by rule 3. the trailing [1] sep, and select 1. the output.

Eventually each sentry [S]n works out to scores of []a that add by rule 2. to the total at the base entry of an Alexa array. By reverse induction, when equal seps are neighbours we can join them directly and add their entries. To clear away these superfluous subarrays we extend rule 4. to merge adjacent sentries, a kind of distribution rule.

• 4.1 _[S]n_[S]1 = _[S]n1 (merge)
• 5.1 _[S][1S]1 4·5.= _[S]a_[1S] (reload)

It is not so economical to let the old rule 4. waste temporarily empty entries. Because in proper radix expressions every separator has a unique position inside an array, we can adapt rule 5. for counted down entries, to let them wait for reload.

Call an algorithm solid, if rules are applied consistently from left to right in the expression. The Alexa radix system is peculiar, because the same result will be reached by a fluid (heterogenic) application of rules. In a fluid evaluation each sentry can be reduced to the left of its parent array independently. This works because secondary void seps [] have to wait for removal by rule 2. at their parent array [ base. In this fluid system some [1]c floats left to base b in its own time, to add its a*c to the total, until all are done.
Solid silicon versus organic fluids, either way a sentry [p]n with sep p index and entry n factor will raise a power a^p*n.

If you stick to solid, there's room in Alexa to simplify expressions further ≡ using rows.
Do away with the first index [p] that counts recursive uploads, and replace all seps on the row by , commas. During evaluation keep these empty comma series ,{k} rigidly in place by reload 5. without clearing, until the end rule 3. drops them from the right.
Subarrays come into play later. They separate multiple dimensions in Beaf systems, which have series of same subarrays. We will prove that nested arrays in row format require half the nesting depth of nested arrays in sentry format, in the next blog.

§2.1. A 4-tuple

A practical evaluation example in linear Alexa to get a taste for her rule system.
We describe entries with arithmetic, and put ≡ them in a comma row.
For a natural format with nested quantifiers, click the @ app.

Alex:a[1111[1]111[11]11[111]1]
  0.≡ 4[1]3[2]2[3]1 row≡ 4,3,2,1 
  ab.= a4,2,2,1 = aa4,1,2,1 = aaa4,,2,1
  5.= a{3}4,a,1,1 =ab.= a{a3}4,,1,1
  5.= a{a3}4,a,,1 =ab.= a{aa3}4,,,1
 =5·3.= a{aa3}4,a,a- =ab.= a{aaa3}4,,a-
 =5·ab:3.= a{a{a}aa3}4  
  ab.= a+4,2,2,1 = a+a+4,1,2,1 = a*3+4,0,2,1
  5.= a*3+4,a,1,1 =ab.= a*a+a*3+4,0,1,1
  5.= a^2+a*3+4,a,0,1 =ab.= a*a+a^2+a*3+4,0,0,1
 =5·3.= a^2*2+a*3+4,a,a-1 =ab.= a^2*3+a*3+4,0,a-1
 =5·ab:3.= a^3+a^2*2+a*3+4 
in Alex:a=2   out = 26
in Alex:a=10  out = 1234  is radix 
  = a^3*1 + a^2*2 + a^1*3 + 4

This output can be read from the Alexa input array, with the direction reversed by ab. addition. Likewise the first row of Blixa piles up pop-star operations.
For system Blixa we copy the rules from our royal matrix Btrix.

Blix:a[4[1]3[2]2[3]1] ≡ 4,3,2,1 
  == aaa4,,2,1 = a,aaa3,1,1
  == a{aaa4},,1,1 = a,a{aaa4}-,,1
   = a{a{aaa4}},,,1 = a,,a{a{aaa4}}-
   = a{a},,a{a{aaa4}}--
  == a{..1..} :a{a{aaa4}}:   
  == a*3+4,0,2,1 = a,a*3+3,1,1
  == a*(a*3+4),0,1,1 = a,a*(a*3+4)-1,1,1
   = a*a*(a*3+4),0,0,1 = a,0,a^2*(a*3+4)-1
   = a*a,0,a^2*(a*3+4)-2 = a^3,0,a^2*(a*3+4)-3
  == a^(a^2*(a*3+4)) 
in Blix:a=2   = 2^40 = 1099511627776 ≈ 1E12
in Blix:a=10  = 10^3400 ≈ 1E3E3
  = a***1+**a**2+*a*3+4 

We've evaluated the same input in Blixa to compare the output numbers. These are larger, because he uploads the accumulated b to right entries after countdown. See the cases of a, here approximated with E notation.
To compare recursions of variable a we either use Knuth's ^ arrows or our pop * stars.
To write powers with nested quantifiers a :double rep: comes in, check the @ app.

§2.2. How big is a row?

Dependent on the algorithm, linear arrays can result in mindbogglingly big numbers.
The limit for the human imagination of large quantities was set by ancient buddhists, who described in a poem the unspeakable tetration 10^^(10^(5*2^120)) we believe.
With the radix resources on the first row Alexa doesn't make it, but Blixa goes higher.
Put Blix:a=10[7,3,0,2,1] and the output a+***a***2+**a*3+7 from his pop-star formula equals 10^^(10^10^37) in up-arrows.

We study a general expression of a sentry in a linear array. The sep index value, equivalent to the linear size (number of commas) in row format, dominates the output.
To switch between rows and sentries (commas and indices), toggle this @ app.

Alex:a[[m]n] ≡ [m]n = [m-]a[m]n-
    == a.[i]a-..[m]n- :m- == a^m[m]n- ,{m}n = ,{m-}a,n-
    == a.,a-..,n- :m- == a^m,{m}n- == a^m*n
Blix:a[[k1]m1] ≡ a[k1]m = [k]a[k1]m-
    == a*{k}a[k1]m- a,{k1}m = ,{k}a,m-
    == a*{k}a,{k1}m- == a*{k}..a :m = a*{k1}m1

A full row of m1 entries a in Alexa is about a^m1 or third entry [2]m1 in Blixa.
Other famous array functions are often faster. We can broadly classify all possible linear array algorithms, so that the linear size a of any class c function is neatly covered by a sentry [k]a (place/value) on first row in a class c1 function:

-2. Dim space of linear array: 1
-1. Len just count entries: a  =Nix []a
0. Nix drop seps, add entries: a*a  =Alexa [1]a
1. Alexa digits in radix: a^a  =Blixa [2]a
2. Blixa tower building: a*{a1}a  =Cca a→a→a
3. Cca Ackermann jumps: a→..a1 :a1  ≈ Beaf{a,a,a,a}
4. Beaf maximal substitution of the predecessor expression.

Given a full array row we can put its value in an early entry. Repeat this k times, nesting row in entry, then we get a function with k entries in a next higher class.
We've grafted a row from class 2 to an Ackermann function, called Graham's Og (years back). By repeated grafting we saw Cca (Conway's chained arrows) in full.

On the linear array Blixa is slower than class 3, but perhaps it can be pushed past Conway's chained arrows after grafting a row or two, we are not sure. The upload of b almost matches that of the predecessor in Beaf, but rule 5. also adds a to b at base, which is a slow start motor. Someone ought to weigh all these rule motives against each other.