Thursday, 29 December 2011

Growing Numbers over the Line

Bright blue curve in dark space, sun visible below the horizon

Today we shoot past the practical physical world with the operation of tetration, which a man uses to raise power towers of variable height. From there on the other superpowers are developed.

Arrows ^.. for comparison  §2.1

In 1976 Donald Knuth invented his arrow notation to express with operators the numbers that result from superexponential functions (constructible by primitive recursion, classified in the Grzegorczyk hierarchy – that some functions increase faster was proven by Wilhelm Ackermann in 1928).

We use arrowheads a^..b in comparisons, and shown below how to evaluate them.  Knuth continued the rules for + * ^ by reducing a superpower with c+1 arrows to a tower of b-1 times the operation with c arrows.

  • a*(b+1) = a+a*b == a+..a*1 {:b} = a+..a {:b}
  • a^(b+1) = a*a^b == a*..a^1 {:b} 
  • a^..1 {c1} = a^..1 {c} == a
  • a^..b1 {c1} = a^..a^..b {c c1} == a^....a {c :b}

The 2nd repetition :b applies to the word from the left start of the Exp up to the 2nd marker dots .. (words in the Exp correspond to factors in the Rep by position).
Same level arrow operations are always associated from right to left.

The thing with arrowheads is that they are ruled by majority precedence, so for their evaluation brackets are needed, soon as 3^^^3 = 3^^(3^3^3) for example.
And if we choose stars ruled by minority precedence (is maximal!), again these cannot be reduced stepwise without brackets, with 3**3 = 3*(3**2) for example.

So to be strict about the characters your algorithm employs, best discard the precedence issue and have operators +.. associate from right to left in all cases! 
Apply a+..b {+:n2} = a*..b {*:n1} = a^..b {^:n} to transcribe intermediate reduction forms of these operations to 1.. and +.. signs (binary, without bracket). 

Further simplify these expressions to a triple format a+c+b {c=n2} or to a file format with a single fixed a plus lots of double recursions ,b,c on top. 
Even further, at the expense of operator compactness, compression of the reduction forms of superpowers reaches its binary low in a basic row function. 

Tetration with higher exponents a,b,c  §2.2

We have set up an elementary system for redoubling and extend its rules slowly.

  • 2.0 a,1,1 = a,a1 1.= a.. {:2^a1} = a*2^(1+a)
  • 1.3 a,b1,1 = aa,b,1 == a..,1,1 {:2^b} = a*2^(1+b+a*2^b)

Three examples how you can reduce such expressions completely. We'll topple the googolduplex 10^10^10^100 here, a number that escapes our physical universe.

  • ♥(6,1,1) 2.= ♥(6,7) = 6*2^7 = 768
  • ♥(2,5,1) 1.= ♥(4,4,1) == ♥(2^6,1,1) 2.= ♥(64,65) = 64*2^65 = 2^71
  • ♥(2,1,5) 2.= ♥(2,3,4) 1.= ♥(4,2,4) 1.= ♥(8,1,4) 2.= ♥(8,9,3) 1.== ♥(8*2^8,1,3) 2.= ♥(2^11,2049,2) 1.== ♥(2^(11+2048),1,2) == ♥(2^(2059+2^2059),1,1) ~> ♥(2^2^2059,1,1) ~> 2^2^2^2059 ~> 2^^4\^11 ~> 2^^6

The last reduction applies the following rules that result in a base 2 tetration.
The approximation given will be worked out generally in section 5.
Assign helper variables u,v,w,.. to store numbers.

  • 2.1 a,1,c1 = a,a1,c 1.== a..,1,c {:2^a}
  • 1.4 a,b1,c = aa,b,c == a..,1,c {:2^b} 2.= u,u1,c- {u=a*2^b} ~> 2^^c\^(a*2^b)

So the three parameters are translated to a tetration 2^^c with a postponed power operation \^P on top, marked by the backslash. This is by convention worked out to a power tower 2^..(2^P) {:c-} to get more detail from P.
Backslashed arrow notation is a convenient tool to compare superexponential functions. However, the few extra steps backslashed \ on top can usually be neglected, given that the direct size of the stairway of a higher superpower is so dominant.

Our superexponential row  §2.3

Let wildcards A,X,Y,Z in a rule substitute for any allowed word (sign sequence) in the expression. We can add some restrictions to the words covered by a wildcard with Regular Expressions, and call such a standard predefined wildcard a wordcard.

Wildcards are allowed to remain empty, with no characters at all. This in contrast to variables n>0 inbetween separators which do not count down to zero. The exception is when an end parameter is deleted (it is thought not to hold a value 0 anymore).

By default the wordcard R will stand in (R: RegExp) for (part of) an array row, made up of parameters pi and single separators , but without begin or end separator.
The regular expression for R shows (when you click it!) it can also be an empty array .

Complete rules for the first row of parameters in my system with multiple parameters and single comma in between. The new upload rule does look beautiful!

  • 0.1 A, = A (comma elimination)
  • 1.0 a,1 = aa, (initial doubling)
  • 1.5 a,1bZ = aa,bZ (redoubling motor) == a..,1Z {a:2^b}
  • 2.2 a,1..R {,1:s1} = a,1..a,R {,1:s} (uploads) == a,1a,..R {a,:s} 1.= aa,..R {a,:s1}

Note that technicalities of greedy vs. lazy selection change the recipe for a wildcard:

Selections are greedy (in Regular Expressions), which means that all subsequent instances of a word to match are to be included, so that none follow right after.
When in the declaration of a rule a wildcard X is placed after a repetition .. of variable size, the greedy match on the left forces X not to start with the repeated token.
Because we've defined a variable as a repetition of ones 1.. {b} the wildcard in rule ♥.1.5 above (is Z) is not supposed to start on 1 (although the rule would still work).
If the wildcard R had not been predefined as a (partial) row, in rule ♥.2.2 the greediness of the left series of ,1 would have required us to adapt R to start on another token.
As soon as a wildcard is declared other repetitions that follow can be lazy again – making it alright for R to start with word a, in the continuation of rule ♥.2.2 above.
This being said, a clean policy will avoid the greedy issue by using well defined wildcards.

After reaching t1 = 256 in blog turf 1 it is now time to create the superexponential record t2 with ten characters up to single , comma between numbers 1..

  • t2 = 11,1,1,1,1 = ♥(2,1,1,1,1) 2.= ♥(2,1,1,3) == ♥(4,2,2,2) 1.= ♥(8,1,2,2) 2.= ♥(8,9,1,2) 1.= ♥(2^11,1,1,2) 2.= ♥(2^12,2^11,2^11,1) 1.4 ~> ♥(v,1,1,1) {v=2^^(2^11)} 2. ~> ♥(v,v,v) ~> 2^^2^^(2^11) ~> t1^^^3 ~> 2^^^4\+1

The number t2 is already unimaginably large, a full tetration step larger than the ancient unspeakable tetration 10^^(10^(5*2^120)) that mahayana buddhism aspired to. 

Clean rules and the basic row  §2.4

In our clean systems:

  • You don't repeat variables – only words consisting of fixed units are repeated.
  • Try to do without brackets – in the primary rules do not nest subexpressions.
  • Although a lower number rule comes before a higher rule in the list (we usually match ♥.1 before ♥.2), avoid dependence on rule preference.
  • Avoid greedy issues with repetitions while using predefined wildcards.
  • Don't rely on Regular Expressions to give back characters (possessive).
  • Don't allow value zero in parameters, but keep final countdowns smooth.

Knuth's arrow operation a^..b can be projected on a basic row of parameters, for the evaluation of superpowers in a system similar to ours.

  • 0. a,b = b
  • 1. a,R,1 = a,R
  • 2. a,b,1R = a,f,R {f=ab R0}
  • 3. a,b.,1..R {:s1} = a.,1..,b1,R {:s} = a,a.,1..,b,R {:s-} == a,a,a.,a-..,b-,R {:s--}
  • a,b.,1..,2 {:s} = a,a.,1..,b {:s-} = a+....a {s :b-} = a*..b {s}

An input expression runs through many reduction forms until a number output is reached. But in upload rule ♦.3 the smallest steps, like a^b = a*a^(b-1), are skipped and Knuth's substitution directly applies, so that a^(b+1) = a*..a {:b}.

In ♦.2 the function motor f adds constant a to the beast b, which is slower than the motor rule ♥.1 doubling its animal a. Also gains a parameter for it lacks a constant and it iterates down to zero instead of 1. Perhaps more significant is that small a instead of big b is substituting the left over entries 1 in the upload series.

We expect to outpace but not in the long run! The higher upload dominates and both upload rules let their best(ial) value substitute for the rightmost entry 1 in the series.
Less powerful rules in the beginning don't matter so much in the end. In section 5 below we will run down the calculation to compare both systems and prove this for the row.

Operators turned superators  §2.5

Vice versa system has an operator format that offers compactness of expression. But instead of counting operators .. we'd rather put their number in a superscript, so you might call them superoperators or superators then. 
In both formats the hearts are left associative and we can park a heart wildcard on the right to hide some advanced operations from view. 
Translate ♥(2,1,1,1) = ♥(2,1,3) = ..  to come to grips with the definition. 

2♥♥♥1 = 231 = 22230 = 223 = 2♥♥3
      = 21222 = 2021122 = 41122 = 81022 = 822
      = 81821 = 2^318 == 2^1110 = 2^1121
      = 2^1112^1120 = 2^1112^11+1 = 2^122^11
     == 2^12*2^2^1110 = 2^2060

For comparison the system with right associative superators s counting stars *.. is shown right. We stub diamonds left, but heart wildcards on either side.
Dare try to wrap your head around these alien abacuses!

a0b = ab                  a0b = ab
as0 = a {s<2 or ≠0}      as1 = a
as10 = a1           {s>0}
asb = as-asb-             asb1 = as-asb
    == a.aí..b- {:s}           == .as-..a {:b}

An incrementor í starts at 1 and is increased by 1 in each next step of a repetition :s.
For example 1*í.. {*í:n} defines the factorial, but in that case order doesn't matter so you can write n! = 1*i.. {*i:n n≥0} as well.

With these special operator notations we like to demonstrate that superexponential numbers can be expressed in a simpler way. 
Pity the party people on planet earth have hijacked superscripts for their petty exponents a2b, but for a machine superscripts and subscripts need to be delimited anyhow, in order to be read from the line. 

Generally there are two options for indexing operators and/or separator signs:

You can expand them directly a[c]b between brackets – or almost directly after the initial , like Bowers did in his Beaf (Jabe is wasting a comma sign there). 
Or you can first introduce them , and then start to count ,.. {c} and append an enumeration ,d;.. or an array ,;d,e,..; (like we did before) or ,`d,e,..` (like we do on this journey), so that a mono-bracket type expansion is eventually reached. 

The main difference between the two systems – the redoubling row versus the basic row system – appears to be that operations are in effect reduced by minority precedence. This is certain to result in larger numbers (example 5*2**3 = 1000) than the majority precedence (where 5*2^3 = 40) which rules system operators.
But how much larger are those numbers exactly?

Evaluating the first row  §2.6

Devise a formula to approximate the first row of system with arrow ^.. operations.
The usual reduction order is ♥:1:2:0 cascading from the left until rules wear out.

  • a,b1,R = u,1,R {u=a*2^b ~ 2^(b+log(a))}
  • a,b1,c1 = u,1,c1 = u,u1,c = u*2^u,1,c ~> 2^u,2^u,c- ~> 2^..u,1,1 {:c} = w,1,1 {w=2^^c\^u}
  • a,b1,c1,d = w,1,1,d ~> 2^^w,1,1,d- == x,1,1,1 {x=2^^^d\^^c\^u} = x,x1,x ~> 2^^x,1,1 ~> 2^^x  = 2^^^(d+1)\^^c\^u 
  • a.,rí.. {:n} ~> 2^..rn1\.^..rì\..log(a)- {n ì :n-}

In this general approximation formula we've used both incrementor í (as explained above) and decrementor ì meta-variables. A decrementor starts at s and is decreased by 1 each step of a repetition :s until finally index 1 is reached.

Now we can compare some Big numbers between systems and find that our is two parameters faster – or one if you don't count the constant 2 item.

a,1.. {,1:s1} = a,1..,a1 {,1:s-} = as11 = asa1
              ~> 2^..(a+1) {^:s a≥1}
              ♦= 2,a1,1..,2 {,1:s1} = 2s1a1

Of course these differences in function speed lose significance once you learn to express row length in the very Big numbers created on the row.

Can there be a final generalization in the evolution of a rule (or rule principle)?
Ponder a peculiar candidate that may answer this fundamental question affirmatively.

The doubling rule ♥.1.0 from day one has been extended a few times to cover further iterations of redoubling on the row.
Now we propose a universal motor rule ♥.1.6 with a restriction on the wildcard (is Z) And meet the dire consequences if we allow any () wildcard Z as an opportunity to create new numbers: fractions, roots, tetration roots, etc…

  • 1.6 a,1Z = aa,Z
  • => aa,,1 = a,1,1 = aa,a
  • aa,,11Z = a,1,11Z = aa,a,1Z
  • aa,,1,..1Z {1,:s} = aa,..Z {a,:s2}

You can choose rule ♥.1.6 as an alternative where usually an upload rule ♥.2 applies. To ponder an example, derive 1,,1,1 = ♥(1,½,½) a mystifying iteration indeed!
We won't go into the field of fractional parameters from odd a,,Z because we are out to build Big numbers in higher dimensions. There we evaluate strictly to whole numbers.

Monday, 26 December 2011

Growing Numbers on the Double

Police officer standing guard at the main doorway of Number 10

Coming days I show you how to build a system to express some extremely Big numbers.
Moving from the bottom up the system's rules are expanded under way, while guarding a general sense of simplicity. Soon these functions increase at record speed and our numbers travel far into the mathematical universe!

We just begin with one unit 1 (raise a finger).

Natural numbers are repetitions 1..  §1.1

Define number variables a,b,c,.. to be filled with ones. A constant t with ten units 1.
Continue counting with fingers 1 (or hands t).

2 = 11
a = 1.. {1:a a>0} = 0+1.. {+1:a}
t = 1111111111 = 10

All variables add naturally, with direct precedence. The addition operator + can be used if you need a lower precedence.
Units minus - (counting down) share this direct affinity with unit 1.

ab = 1..1.. {1:a 1:b} = a+b = ba
1- =   = 0 = -1
ab-.. {-:b} = a

We implied the repetition of characters using a special RepExp.A notation.

{ RepExp } notation

A. Here W:n signifies a word repetition (Rep), to substitute n times the word W in place of W.. in the preceding expression (Exp). We call this a RepExp, a simple form of Regular Expressions (RegExp), ideal for working out recursive functions.

Instead of grouping words with brackets like in RegExp or rehashing words in the Rep as above, we can use dots to delimit and select specific character sequences.
Arbitrary words (fitting for the Exp) are represented by wildcards in capital letters.
Count down the Rep factor to turn a RepExp step by step into a normal expression.

W.. {:n2} = W.W.. {:n1} = WW.W.. {:n}
== A.W.. {:1} = AW
A.W..M.X.Z {:1:} = AWMXZ
A.W..M.X.Z {:n1:} = AW.W..M.X.XZ {:n:}

Option B. when W in the Exp holds a single sign, just write the factor n in the Rep.
C. When W.. starts at the left end or from .W.. dot selection, put :n in the Rep.
D. With words repeated both to the left and right end (or dot), write :n: in the Rep.

With multiple repetitions, the words to target in the Exp correspond to factors in the Rep in the same order. To avoid confusion there's the canonical option:
E. The Rep clause can also be put inside the Exp, right after a word selected by a free left dot .W{:n} or after a single character w{n} as usual in RegExp.

As we venture to accomplish great things, the fun is to maintain the utmost frugality. The turf records (Dutch: turven = to count) defined in each chapter are strings of length ten – ten character places to store a larger number than before. Starting with the sign 1 we've now turved t=10.

One separator , to function as a redoubling operator  §1.2

Introduce a single comma , to separate two variables within an expression. Then reduce them by rules ♥.1 to repeatedly double the left value (starting with a) while the right iteration counter (initially b+1) is decremented.

  • 1.0 a,1 = aa = a*2
  • 1.1 a,b1 = aa,b == a..,1 {:2^b}

An alternative way to define rule ♥.1 of the operation of redoubling.

  • 0.0 a, = a = ♥(a,0)
  • 1.2 a,b = aa,b- ==0. a.. {:2^b} = a*2^b

Here a countdown is written by appending the unit minus - to parameter b so that it is reduced 1- step by step == until the final zero falls away gracefully (a zero gap must not subvert the algorithm).
Also on every iteration step each unit in first entry a is copied and added next to it. Working with integers this puts the output 1.. on a scale a*2^b of binary powers.

t1 = 11,1111111 = ♥(2,7) = 2^8
   = ttttttttttttttttttttttttt111111 {t=1111111111}

Your ten-o-maniac has managed to squeeze a byte 256 in ten places in the above two parameter notation. This restriction on expression size requires that b=t-1-a.
You may improve on his number by taking the 1.. not as characters but as real sizes, so that for all restricted ab the maximum is reached when e^(1/a)=2 so a~1.44.
In the redoubling graph [plot in Sage] for the length t-1=9 you see the real maximum at 271.7 pushing just a teeny 60% higher than our present discrete turf t1=256.