Ψ.2. Up to the Ackermann numbers

chapter 2.6, edit 0.2.9
published: 2011-06-24
updated: 2011-12-30

# 2.6. Superpower structures

Necklace with a gold and a silver serpent biting each other's tails

ΓΝΩΘΙ ΣΕΑΥΤΟΝ

"Know Yourself"

written in the forecourt of Apollo's temple in Delphi
– Pausanias 175 AD

"Kind people find that they are cruel, brave men that they are really cowards. Confronted with their true selves most men run away screaming!"  (as lectured by prof. Engywook)

§2.6.1. Group by spaces to make operators

Starting with units 1 and zeroth separators (meaningless spaces of any breadth) numbers are built like 11 = 2 which is the simplest method of construction. Number variables a consisting of countable ones 1.. {1#a 0*} keep count of anything, even of separators.
This expresses all natural numbers – numbers used for counting – in what could be called the initial row.

Now to go over to dimensions, let + be the single separator defining natural numbers a = 1+.. {1#a} on the first row. Then separate rows of equal length a with double separators ++ forming a square of size a^2, followed by separators +++ for a cube of equal sides a^3, etcetera… Until at last +.. {+#b} counts the exponential structure we've met before in chapter 1.5.
Follow two expressions that reduce to 1111111111111111 also known as 16 or sweet sixteen.

4^2 = 1+1+1+1++1+1+1+1++1+1+1+1++1+1+1+1 (built from 1)
2^4 = 11+11++11+11+++11+11++11+11++++ (built from a=2)

All structural gaps +.. are equally devoid of meaning – their only property is their number, but this doesn't relate. The actual number such an exponential hypercube reduces to is solely determined by the blunt total of units 1.. stored inside.
Words of two character types, where 1 bears substance and the additive spaces + sprinkled in between are equally empty, can be seen as the ground state of ordered dimensional structures. Such a ground state is qualified by the exponential shorthand a^b and quantified by a number 1.. that remains when the empty spaces are dropped.

a^b = 1+.... {+..#b #a} = 1.... {..#b #a 0*}
    = a*... {a#b} = a... {a#b 0^}

Our default context 0* is additive, but expressions X can be put in arrow context 0^ so that neighbouring numbers are multiplied. Because addition is resolved instantly, minority precedence for star operations a*..b*..c is more natural, while we evaluate arrows a^..b^..c by majority precedence as usual.
When we allow for brackets () to be nested, both types of operations – majority arrows and minority stars – can be used to express the same numbers similarly. Note that two bracket characters are perfectly sufficient here and that the introduction of another bracket sign wouldn't help to boost expressiveness.

We can always reduce composite stars or arrow operations to a format with a single operator, with the difference that the arrow evaluation requires nested brackets and the stars don't. Stars only use brackets in their evaluation when we substitute in the smallest of steps instead of using Knuth's method of direct substitution.

2***3**3 = 2***3*`3**2`
         = 2***3*3*`3**1` = 2***3*3*3
         = 2***3*3`3*2` = 2***3*9 = 2^^27

2^^3^3 = (2^2^^2)^3
       = (2^2^2^^1)^3 = (2^2^2)^3
       = (2^(2*2))^3 = (2^4)^3 = 16^3

The expressiveness of our system changes by applying the restriction that only one type of bracket ` or no bracket sign at all may be used. Numbers concisely expressible as a(b*(c**d)) versus ((a+b)*c)^d for example, in most cases have to be notated almost completely as 1.. natural number, if a ban on brackets was declared.

Suppose a number expression has a certain maximum description length – a physical truism – then minority stars by nature (without bracketing) will allow for the expression of larger numbers, while majority arrows will produce more smaller numbers. The result of evaluating smaller operators first is to increase the capacity, while evaluating larger operators first increases the resolution of expressions with a given word length.

§2.6.2. Are rows as good as dimensions?

Any two characters that are both countable can form a dimensional structure. Here we build further using the arrow ^ sign in between number variables as a countable operator – that is a separator character ^.. with a functional purpose, where (in a classical sense) the functions are enumerable following a specific rule.
The first arrow row a^... {a#b} erects a power tower, where every higher power counts the number of ground state dimensions of the exponent on the storey below (moving from right to left). This amounts to tetration a^^b which can be extended to a similar row a^^... {a#b} for the next superpower a^^^b, etcetera…

a^..b1 {^#n} = a^..b\*..a {^#n *#n} = a*.... {*#n a#b1}

Notice the row upon row structure which is the natural way to express the superpower series of functions (and the way Knuth founded his arrows). We could have made our first stop at multiplication a.. {a#b 0*} and do away with the concept of dimensions, which doesn't seem to create significantly bigger numbers.
But is that so? How much faster would our function series be if we'd construct it dimensions upon dimensions? We will work this out for an up-arrow operator ruled by minority precendence, to establish what looks like an upper bound for such construction methods with dimensional modules.

ab = 1+.... {+..#b #a} = a**b
a↑↑2 = (aa)(aa) = a**a**a1
a↑↑b = (aa).. {(a↑a)#b} < a***b\**a2 < a***b2
a↑↑↑2 = (a↑↑a)↑↑(a↑↑a) < a****3\2
a↑↑↑b = (a↑↑a)↑↑.. {(a↑↑a)#b} ~ a****b1
a..b {↑#c} ~ a*..b1 {*#c1}

So there's not much gained from using dimensions as building blocks. After the row we get for free by skipping multiplication and the one iterator step extra at tetration, the increase becomes ever smaller and converges to the speed of building row upon row.
Taking into account that dimensional construction is rather complex, this shows that Knuth's arrows (simple repetition of previous operations) present a practically optimal algorithm for creating superpower-size numbers.
The problem this illustrates is, whether functions of any type are best defined with a single row of parameters and then expanded upon row upon row, or if dimension-type function arrays (such as those of Bowers and Bird) will form an indispensible tool in the construction of Big numbers.

It remains to be seen whether at some stage an expansion of the parameter space to multiple dimensions becomes necessary. And generally if it's any use for sign types beyond 1 to be potentially countable – foremost if we should allow countable operators like ^.. and separators ,.. in the construction of functions?
Instead an initial subscripted coefficient ^1..; {1#m} at the start of a potentially very long list of parameters 1.. separated by single , commas, perhaps subscripted to some fixed depth, may very well do. Though subscripts are convenient for human eyes, in our algorithms parameter levels will be delimited by a single ; semi-colon, functioning as an end bracket for the sequence started by the nearest unpaired ^ or , sign.

a^;b = a... {a#b 0^}
a^n1;b = a^n;... {a#b}
a^n01,..,np;b = a^n0,..,np;... {a#b}
a^ni,nji,...;...;b {ni#p mji#q} etc.

Of course such subscripted structures for bracket-like operators require further definition so we may them to simpler expressions and eventually to natural number… Important is that every separator sign is not just countable – by a first coefficient – but can be expanded by subscripting it with a row of iterator parameters.
Or would you prefer to have dimensions?

§2.6.3. Tetration program with loops

In this chapter we'll write a small interactive program for the function of tetration that you can try out below.
The operation of tetration *** requires n=3 nested loops, and then it's easy to see how this program can be extended to any specific superpower *.. {*#n} by writing code for n nested loops.

In our Auryn programming syntax the loop function comes in place of the for statement in a C-based language. The first loop(argument counts the number of times the code block below (the second , function type argument) is to be executed. That block covers all lines of code up to the closing bracket ) of its level, recognizable by the indentation.
When the iterator argument is not greater than 0 the loop terminates and the processing moves over to the next line. This eventually happens because the iterator is counted down by 1 at the end of every routine.

The bonus of our program is that the lengthy calculation of a tetration a***y can be interrupted any time a loop statement occurs, with the subtotal and the current iterator states preserved in the values of the array.

Tetration by iterated addition
T := [a,0,1,1,y] /* initializes array */
/** loop functions, in C: while(Ti>0) { .. Ti--; }, math: G(t,F) */
loop(T4, /* repeat powers */
loop(T3, /* multiplications */
loop(T2, /* additions */
T1 += T0) /* add b := b + a ←Tracer */
T2 := T1 /* trace: a,a,a^2,..,a^a,.. */
T1 := 0) /* reset */
T3 := T2 /* trace: a,a^^2,..,a^^y */
T2 := 1) /* reset */
T4 := T3 /* reset T3 := 1 and return */

Press Go to watch the trace of the calculation (evaluation train) proceed as the values of array T change in the innermost loop. There the total b in T1 accummulates by repeatedly adding a or T0. When the loop is done this subtotal seeds the counted down iterator(s), causing the same loop(s) to repeat an increasing number of times.
Because item a never changes it is omitted from the moving print line below.

Tracer ← a^^y

Run the program and the rules for the reduction of all superpower expressions become apparent. Tetration a***y requires an array of 3+2 entries, likewise superpowers a*..y {*#n} start off with a fixed size n+2 array.
Every run-time array stores an intermediate state, so one number is expressed by many different arrays.

Keep the Tracer in mode 1 and observe the intermediate values after setting tetration to 3^^3 there. Each entry in array T is assigned a specific task. In order of significance for the result:
 [ item a, subtotal b, + operand count, * operand count, ^ operand count ]
Each array follows from a corresponding expression.

3^3^3 = [3,3,1,1,3]
3^(3*3*3) = [3,3,1,3,2]
3^(3*(3+3+3)) = [3,3,3,2,2]
3^(3*(3+6)) = [3,6,2,2,2]
3^(3*9) = [3,9,1,2,2]
3^(3+3+3+3+3+3+3+3+3) = [3,3,9,1,2]
              == 3^27 = [3,27,1,1,2]
       3*...3 {3*#26} = [3,3,1,27,1]   etc.

In the expressions the rightmost operand b changes, while all other operands have a=3 as value.
Notice that we skip over states like 3^3^^2 and 3^(3+3*8) because the program emulates Donald Knuth's principle of inserting a series of smaller operations at once. So that 3^^3 resolves to 3^3^3 directly, not via 3^3^^2 and then 3^3^3^^1 etc.
Because of Knuth's substitution the larger operators ^.. stay left of the smaller, so the translation from array to expression is kept straightforward and unambiguous.

§2.6.4. Natural array functions

The projection of superpowers on a function of a row of parameters follows. The first two axioms express the array when the Tracer is set in mode 1, provided that item a>0 and subtotal b>0 as it is in the innermost loop. The last two axioms help reduce the result to a single number.

  • Superpower row [mode 1]
  • a,,Z = a,0,Z = a,a,Z =>
    a,,1 = a,0,1 = a,a,1 = a,a = a
    a,,,1 = a,0,,1 = a,a,,1 = a,a = a
  • a,b,1,...,2R {1#k1} = a,,1,...,b,1R {1#k} (show rule before)
         = a,a,1,...,b,1R {1#k} (upload rule)
         = a,a,1,...,a,b-,1R {1#k- b>1}
        == a,a,a,a-,...,b-,1R {a-#k- a>1 b>1} (full upload)
  • a,b,2R = a,ab,1R (main rule)
  • a,R1,1,... {1-#k} = a,R1,... {1#k} (drop final 1)
                     == a,R1
  • a,b = b (boolean select)
  • a,b,c1 = a,ab,c == a,a...b,1 {a#c} = a*c + b (examples)
    a,,b = a,a,b = a*b
    a,X1,,..1 {,#k} = a,X1,..1 {,#k>0} == a,X1,1 = a,X1
    a,b1,,c1 = a,,b1,,c = a,,b-,11,,c == a,,11,1...1,,c {,1#b-}
             = a,,1...1,,c {,1#b1} = a,a,1...,2,,c {,1#b}
             = a,,1,...,a,1,,c {1#b-} = a,a,1,...,a,1,,c {1#b-}
             = a,a,1,...,a,,c {1#b-} = a,a,a,a-,...,,c {a-#b-}
            
    = a,a*..a,,c {*#b} ~ a→ab→c1→2 = a→ab→(a→ab→c→2)
    a,,,b1 {b>0} = a,a,,b1 = a,a*..a,,b {*#a}
    a,,,2 = a,a,,2 = a*..a {*#a}

The main rule is the motor of an algorithm because it produces larger parameter values all the time. But here the main rule is extremely slow, it just increments b by an amount a which is constant in value.
On the other hand, because this rule does not require extra brackets, the algorithm manages to employ only 1.. and single , characters. A superpower expression goes in, a number comes out, but the program doesn't need any extra sign resources (except the four axioms) inside its black box.
Then it's the merit of our archetypical upload rule that superpower speed is realized on the row. Upload rules are extremely powerful, even when their load – the subtotal parameter b – is squandered, QED.

Check your uploads

Suppose b wasn't replaced in the upload rule above but that it would stay. Then to show that not much is gained from the improved rule, take 3,27,1,1,3 or 3^3^27 and reduce it to 3,27,27,26,2 or 3^(3^25*(3*26+27)) when translated, instead of the 3,3,3,26,2 or 3^(3^25*(3+3+3)) which we used to have.
Compare the old exponent 3^27 with the new exponent 3^25*3*29 ~ 3^29.065 and consider this – the larger the value of the uploaded parameter, the less it matters whether it stays or is replaced by a constant value.
However, the effect of adapting a rule is always cummulative, so if we start with 3^^4 the superpower upload resolves to about 2^^5 while a brutal upload rule defined by a,b,1,...,2R {1#k} = a,b,...,1R {b#k1} fetches in the order of 2^^7 as you can check here.

3^^4 =
3^3^3^3 =
3^3^27 = {a£b : log(b)/log(a)} =
2^(2£(3^3^27)) =
2^(3^27*2£3) =
2^(2^(2£(3^27))*2£3) =
2^(2^(27*2£3)*2^(2£2£3)) ~
2^(2^(27*1.585)*2^(2£1.6)) ~
2^2^(42.8 + 0.7) ~
2^2^43.5 ~
2^2^2^5.44 ~
2^2^2^2^2.44 ~
2^^5\+.44
  3,4,1,1,1,2
    4,4,4,4 ,1
    7,3
    10,2
    13,1
    13,13,3
    16,12
 .. 12*4+1,1
    49,49,2
 .. 48*4+1,1
    193,193,1
 .. 192*4+1,1
    769,769,769,3
 .. 768*4+1,1
 .~ 768*4^769,1,1
  ~ 4^774,4^774,4^774,2
 .~ 4^(774+4^774),1,1
  ~ 4^4^774,4^4^774,4^4^774 ,1
 .~ 4^(4^774+4^4^774) ,1,1
  ~ 4^4^4^774
  ~ 4^4^4^4^4.8 ~ 4^^5\1
  ~ 2^(2*2^(2*2^(2*2^(2*4.8))))
  ~ 2^2^2^2^10.6
  ~ 2^2^2^2^2^2^1.77 ~ 2^^7\-.23
likewise against a^^^b for comparison:
  a,b,1,1,1,1,2
    b,b,b,b,b ,1
    ab,b-
 .. (a*b-)b,1
  ~ a1*b-,v,b-  {v1:a1*b-}
    av,v-
 .~ a1*v-,1
  ~ a1*a1*b-,a1^2*b-,b--
 .. a1^b*b-,1,1
  ~ b*a1^b,v,v,b-  {a~b v2:a1^b1}
 .~ v*a1,1
 .~ v*a1^v,1,1
  ~ a1^b1(a1^b1),a1^a1^b1,a1^^2\^b1,b--
 .~ a1^a1^a1^b1,1,1
 .~ a1^^b\^b1,1,1,1
  ~ a1^^b1,v,v,v,b-  {v3:a1^^b1}
 .~ a1^v,1,1
 .~ a1^^v,1,1,1
  ~ a1^^a1^^b1,a1^^^2\^^b1,a1^^^2\^^b,b--
 .~ a1^^^3\^^b,1,1,1
 .~ a1^^^b\^^b ,1,1,1,1
  ~ a1^^^b1
when the upload rule sends b to the rightmost index
saving subtotal b in all iterators barely increases
superpowers a^..b {^#c} to about ~ a1^..b1 {^#c a~b}

From our program for superpowers with the Tracer set in mode 0, which counts every iterator entry back to zero, we can also construe an array function, but it doesn't appear to be shaped like a row.
In our 1.. number system a value of p=0 causes an iterator parameter ,p, to drop away and its neighbouring separators ,, to simply add up. Because this can happen to multiple parameters in a row the separator commas ,.. become countable, albeit (arguably) in one particular place (at the second comma).
It's there where this array function starts to become pseudo-dimensional.

Now compare this type of dimensionality function definition Dimensional form is what we have with superpowers expressed as a*....b {*#ci a*..#n} by star operators (note that this form allows ).
Luckily for the row concept

Under 2012 Construction

  • Superpower row [mode 0]
  • X, = X (comma elimination)
    so  A1,..0 {,#k} == A1
  • a,b = b (right selection)
    so  ,b = 0,b = b
  • a,b,1Z {b≥0} = a,ab,Z (main motor)
    so  a,b,c = a,ab,c- == a...b {a#c} = a×c+b
        a,,b = a,0,b = a,a,b- = a×b
  • a,b,,1Z = a,,b,Z (add iteror upload)
            = a,0,b,Z ={b>0}= a,a,b-,Z
                  ={b:0 Z:z}= a,0,0, = 0
               ={b:0 Z:z,1Y}= a,0,0,0,1Y = a,,,,1Y
    so  a,b,c,d == a,a×c+b,,d = a,a,a×c+b-1,d-
        = a,a,a×(a×c+b)-1,d-- == a,a,a^(d-1)×(a×c+b)-1
                               = a^d×(a×c+b)
        a,1,0,b = a,0,1,b- = a,a,0,b- = a^b
  • a,b,..1Z {,#k3} = a,1,..b,Z {,#k2}
                    = a,1,..1,b-,Z {,#k1>1 b>0}
                   == a,1,,1,..b-,Z {,#k>0}
                    = a,,1,..b-,Z {,#k1}
                    = a,a,..b-,Z {,#k2} (super upload)
                    = a,a,..a-,b--,Z {,#k1 b>1}
                   == a,a,a-,a--,..b--,Z {a--,#k}
    so  a,,,,111Y = a,0,,,111Y
                = a,1,,0,11Y = a,1,,1,1Y = a,,1,,1Y = a,a,,,1Y = a,1,,a,Y = a,,1,a-,Y = a,a,,a-,Y = a,,a,a--,Y = a,a,a-,a--,Y

Listing in order of significance: item t0>0, store t1≥0, then t2 counts + operators, t3 counts * operators, next terms tn4 count ^.. {^#n1} operators, in a superpower expression which applies Knuth's substitution.
We work out an example expression and then generalize it for star *.. operators. click here!

11,111,,,,,1 = 2****3 = 2,,,,,3
11,11,,,,11 = 2***2***2 = 2,,,,2,1
11,11,,,1,1 = 2***2**2 = 2,,,2,,1
11,11,,1,,1 = 2***2*2 = 2,,2,,,1
11,11,1,,,1 = 2***(2+2)
11,1111,,,,1 = 2***4 = 2,,,,4
11,11,,,111 = 2**2**2**2 = 2,,,2,2
11,11,,1,11 = 2**2**2*2 = 2,,2,,2
11,11,1,,11 = 2**2**(2+2)
11,1111,,,11 = 2**2**4 = 2,,,4,1
11,11,,111,1 = 2**2*2*2*2 = 2,,2,2,1
11,11,1,11,1 = 2**2*2*(2+2)
11,1111,,11,1 = 2**2*2*4 = 2,,4,1,1
11,11,111,1,1 = 2**2*(2+2+2+2)
11,1111,11,1,1 = 2**2*(2+2+4)
11,111111,1,1,1 = 2**2*(2+6)
11,11111111,,1,1 = 2**2*8 = 2,,8,,1
11,11,1111111,,1 = 2**(2+...2) {2+#7} ..
2,16,,,1 = 2**16 = 2,,,16
2,2,,15 = 2*...2 {2*#15}
2,2,1,14 = 2*...(2+2) {2*#14}
2,4,,14 = 2*...4 {2*#14}
2,16,,12 = 2*...16 {2*#12} ..
2,256,,8 = 2*...256 {2*#8} ..
2,4096,,4 = 2*...4096 {2*#4} ..
2,16384,,2 = 2*...16384 {2*#2} ..
2,32768,,1 = 2*...32768 {2*#1} = 2,,32768
2,2,32767 = 2+...2 {2+#32767}
2,65534,1 = 2+65534
2,65536 = 65536
1... {1#65536}

a,b,tí,... {tí#c í≥2} =
    a*......b {a*....#c *#ì≥0 a*..#tì2}

Under 2011 Construction

Yet it is a remarkable algorithm for two reasons. It falls right between the 1..^.. (dimensional) and bigE 1..,1..,1.. (3 numbers)

§3.?.?. Effective computability

Hello world. Another Ackermann function

Superpowers
T := [a,0] /* initializes array */
/** recursive loop function */
loop(c, /* superpowers */
itf(c=1, /* if true then */
T1 += T0, /* addition */
to loop(c-1) /* else recursion */
Tc := T1 /* a,a,a^2,..,a^a,.. */
itf(n<2,
T1 := 0,
T1 := 1) ) /* if n>1 then */
)
 
Superpowers
T := [a,0] /* initializes array */
/** recursive loop function */
loop(c, /* superpowers */
if(c=1, /* if true then */
T1 += T0) /* addition */
else( /* if n1 then */
to loop(c-1) /* recursion */
Tc := T1 /* a,a,a^2,..,a^a,.. */
if(n<2, T1 := 0)
else(T1 := 1) ) /* if n>1 then */
)
 

Hello world.