Thursday, 3 July 2014

Alexa 1st - Radix Structures

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.

§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.

  0. 4[1]3[2]2[3]1 row≡ 4,3,2,1  
  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  
  == 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,n-
    == a.,a-..,n- :m- == a^m,{m}n- == a^m*n
Blix:a[[k1]m1] ≡ 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:

  1. Dim space of linear array: 1
  2. Len just count entries: a  =Nix []a
  3. Nix drop seps, add entries: a*a  =Alexa [1]a
  4. Alexa digits in radix: a^a  =Blixa [2]a
  5. Blixa tower building: a*{a1}a  =Cca a→a→a
  6. Cca Ackermann jumps: a→..a1 :a1  Beaf{a,a,a,a}
  7. 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.

No comments:

Post a Comment