Ψ.2. Up to the Ackermann numbers

chapter 2.1, edit 0.2.9
published: 2011-01-07
updated: 2011-12-30

# 2.1. Super-calculation

Arrays of men with overcoats and bowler hats floating through the suburbs

The great teacher said,
      "The supreme ineffable Way of all enlightened ones involves ages of effort, carrying out what is difficult to carry out, enduring what is difficult to endure. How can you hope for true religion with little virtue, little wisdom, a shallow heart, and an arrogant mind? It would just be a waste of effort."

– Bodhidharma to Hui K'o
Transmission of Light

§2.1.1. Backslashing

To compare the size of two very large numbers we can often only aim for an approximation, specially when we have to deal with expressions of different algorithms (different sets of rules). An unknown algorithm would be explored starting with superpowers (our stars or Knuth's arrows) as a benchmark for example. Step by step the value of the unknown expression is build up and translated into the familiar benchmark format.
This chapter explains backslashed operations. With backslash notation we write compound expressions more easily, keep pace with the reduction train of new algorithms and express Big numbers with just the right precision.

The main rule in an algorithm typically replaces an operation ..b1 {×#c1} by a series of lower operations, either in one sweep .... {×#c a#b1} or by iterating over a substitution step ..(a×..b) {×#c ×#c1} where the number of iterations b equals the number of lower operators ×.. {×#c} in the resulting series.
Each term in this series of host operation H can be addressed with an index k starting at index k=1 (this may be omitted). Then a guest operation G is invited by backslashing H\k'G which applies G to the (subscripted) kth term alone, or by H\k"G to apply G to that part of the series starting at the (superscripted) kth index.

We always count terms from the top H\ (the right) of the series where the value has most impact, because iterators b are nested from right to left (if substituted as above). On other occassions (nesting from the left) you may like to address terms from the bottom up \H but only if there's no risk of mistaking the guest for the host. We dare use the prefix backslash only when G adds a number or variable.
The backslash is resolved when the host iterator is counted down and the guest joined in with a subexpression at the invited position, as follows…

b\a**3 = b+\1'a^3 = a**3\3'b = ab*a*a 
a^^3\**b = a^^3\1'^b = a^^3\1"^b = a^a^a^b 
a^^4\2"*b = a^a^(a^a*b)
a^^5\3'*b = a^a^(a*b)^a^a 

a***3\1'*3\2'2\3'b = ab**a2**a*3 
a***3\*3\*b = a***3\(*3\*b) = a**a**aa(a*b) 
            = a**a**a*b2 = a***3\*b2 

a^^3\2"(***2\b) = a^(a^a)^(a^a+b) 
3^^2\\2'^a = 3^3\2'
**a = 3*(3**a)*3 

A party of all kinds of backslashed guests is less practical, but can be fun!
Note that star operations *.. are ruled by minority and arrows ^.. by majority precedence. But the original backslashed operations stay unresolved, until the host has shed a star and it's time for a backslashed operation to step in, then it's granted the highest priority.
A few more instructive examples – backslashes are particularly useful when iterations can get long.

7^^7\×11 = 7^7^7^7^7^7^77
p****1111\***111\**11 = p***p***p***p**p**p*p
5^^n\(^2+2)×2\n'^2 = 25^5^...^54 {5#n--}
a***b2\b'1 = a**a**a1**a... {**a#b}
2^^^3\\2"^5 = 2^^4\2"^5 = 2^2^(2^2)^5
         ;  = 2^2^4^5 = 2^2^1024 = 2^^3\^10

With  a^^b1\2'1 < a^^b1\1 < a1^^b1  we put our new backslash notation to good use.
The next subchapter zooms in on tetration and shows some advanced uses of backslashing.

§2.1.2. Pushing beyond powers

We start with superpowers and calculate a few pentation squares m****2 = m^^m and find a rule to approximate tetration. We use brown here to highlight the real exponent, corresponding to an approximation rule with an integer coefficient. After <~ comes the larger and significantly better approximation, closer to m^^n at the end.

4^^4 = 4^4^4^4 ~ (4^3.17)^^3 ~ (4^252.)^^2
5^^5 = 5^5^5^5^5 ~ (5^4.12)^^4 ~ (5^3120.)^^3

m^^n ~> (m^(m-1))^^n-
     <~ (m^(m^m - m))^^n--
     <~ (m^(m^^d - m^^(d-1)))^^(n-d) {0<d<n-}

We'll compare expressions of the form (a*..b)*..c with those of the form a*..bd and with those beyond. If you just want to get the big picture you can skip the original details!

  • (a*b)*2 = a*bb  extends to:
    (a*b)*b = a*b^2  generally:
    (.a.)*b.. {#n#} = a*b^n
  • (a^b)^2 = a^(b*2)  extend:
    (a^b)^b = a^b^2  generalize:
    (.a.)^b.. {#n#} = a^b^n
  • a^^b1  =  a^a^^b <~
        (a^^2)^^2 = a^a^a1
        (a^^3)^^2 {a↑ω} = a^a^(a1^a /ê)
        (a^^b)^^2  =  a^a^(a^^(b-1)+a^^(b-2)) <~
             1\3'a^^b1 {b>2}  =  a^a^(a+1)^a^^(b-2)
                
    < a^^b2  extend to:
  • a^^bb- <~
        (a^^b)^^b  =  a^(a^b-*..a^^b.) {#b-#} <~
        (a^^b)^^3 ~ a^a^a^a1^a^^b-- = a^^(b+2)\b-'1
             a^^(b+b-1)\b-'1  =  1\b1'a^^bb-
                
    < a^^(b*2)  generalize:
  • a^^b(b-*n-) <~
        (.a.)^^b.. {#n#} <~
        ((a^^b)^^b)^^2 ~ a^^bb-^a^^bb- ~ a^^bb\b-'1
        ((a^^b)^^b)^^b ~ a^^bbb--
             a^^((b-1)*n+1)\b-'1 < a^^(b-*n)2
                
    < a^^(b*n)

From three arrows onwards these comparisons are exceedingly difficult to resolve. It can be guessed from the estimated ranges above that pentation ^^^ leaves very large holes, where most numbers are lost in jeopardy.
Consider the following operations – in between there are widening number holes looming.
Again these equations won't stop at anything – click here!

      3^^^3 = 3^^3^^3 = 3^^(3^27)  <~
(3^^^2)^^^2 = (3^^3)^^3^^3
            = 3^^3^...3^^3 {#(3^^3)-}
            ~ 3^^3^...3^^4 {#(3^^3)--}
            ~ 3^^(3^27+2)  <
    3^^4^^3 = 3^^(4^256)  <
    3^^3^^4 = 3^^(3^7625597484987)  <
      3^^^4 = 3^^3^^(3^27)  <~
(3^^^3)^^^2 = 3^^^3^^3^^^3
            = 3^^^3^...3^^^3 {#(3^^^3)-}
            ~ 3^^^3^...3^3^^3^^3 {#(3^^^3)--}
            ~ 3^^^3^...3^^(2+3^27) {#(3^^^3)---}
            ~ 3^^(3^^3^^3-1+3^27)
 <~
(3^^^2)^^^3 = (3^^3)^^(3^^^2)^^^2 (substitute and..
            ~ 3^^(3^^(3^27+2)+2) ..iterate as in line 2 above)
            ~ 3^^^4\2"+2
 <
(3^^^3)^^^3 ~ (3^^^3)^^3^^(3^^3^^3+3^27-1)
            ~ 3^^(3^^(3^^3^^3+3^27)+3^27)
            ~ 3^^^5\3"+3^^3

We boldly generalize this to a comparison formula for superpowers. Calculations you can find in the <page source>.
In the cases below let ^.. {^#c c>2} and its reduction *.. {*#c} continue from where we left, after tetration. Mark the specified repetition dots ... in violet. As usual arrows take precedence before stars.

  • a^..b1  =  a*..a^..b <~
       (a^..b)^..2  =  a^..b*..a^..b <~
           (a^..b-)\2"a^..b1 < 1\3'a^..b1 < a^..b2
  • a^..bm  =  a*.. ...a^..b {#m} <~
       (a^..b)^..m1  =  a^..b*.. ...a^..b {#m}
  • a^..(b*n)1 <~
       (.a.)^..b1.. {#n#} <
           a^..(b1*n)    .