“On the shoulders of giant numbers”
http://www.allergrootste.com/big/book/ch2/ch2_6.html
bigΨ
Ψ.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
ΓΝΩΘΙ ΣΕΑΥΤΟΝ
"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
.
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*... {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…
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 precedence,
to establish what looks like an upper bound
for such construction methods with dimensional modules.
a↑↑2 = (a↑a)↑(a↑a) = a**a**a1
a↑↑b = (a↑a)↑.. {(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^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.
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,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.
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 n≠ 1 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.
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, take3,27,1,1,3
or3^3^27
and reduce it to3,27,27,26,2
or3^(3^25*(3*26+27))
when translated, instead of the3,3,3,26,2
or3^(3^25*(3+3+3))
which we used to have.Compare the old exponent
3^27
with the new exponent3^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 about2^^5
while a brutal upload rule defined bya,b,1,...,2R
{1#k}=
a,b,...,1R
{b#k1} fetches in the order of2^^7
as you can check here.