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