Linear array notation

Next: Extended array notation

Linear array notation (LAN) is the first part of my array notation. It’s the simplest and weakest one.

Definition

First, the linear array notation looks like this:

s(a,b,c,…,z)

where positive integer a,b,c,…’s are called entries; the , is comma with ASCII = 44. And the “s” means that it’s a “strong” array notation.

The first entry of array notation is called base, the second entry is called iterator.

String A is before B iff A is written left to B. A is after B iff B is before A.
String A is immediately before B iff A is before B and there’s no such C that A is before C and C is before B. A is immediately after B iff B is immediately before A.

Rules and process

Every array results in a number. To solve it, we need some rules and processes as follows:

  • Rule 1: (base rule – only 2 entries) s(a,b) = a^b
  • Rule 2: (recursion rule – neither the 2nd nor 3rd entry is 1) s(a,b,c #) = s(a, s(a,b-1,c #) ,c-1 #)
  • Rule 3: (tailing rule – the last entry is 1) s(#,1) = s(#)

where # is a part of array (a string of entries and commas, it can also be empty).

If none of the 3 rules above applies, start the process shown below. Note that case B is terminal but case A is not. First start from the 3rd entry.

  • Case A: if the entry is 1, then you jump to the next entry.
  • Case B: if the entry is not 1, then
    1. Change the “1,n” into “b,n-1” where n is this non-1 entry and the b is the iterator.
    2. Change all the entries before them into the base.
    3. The process ends.

Explanation

For array notation with only 2 entries, rule 1 applies, and s(a,b) = a^b – that’s an exponentiation.

3-entry arrays

The simplest 3-entry arrays are s(a,b,1), and rule 3 applies, so s(a,b,1) = s(a,b) = a^b.

The next term is s(a,1,2). Here rule 1~3 don’t apply, so we need to start the process. First we look at the 3rd entry – it’s already a non-1 entry, so we meet case B. Then change the “1,2” into “b,2-1” = “1,1” (here iterator is 1), and “the entries before them” only contain the base a, so s(a,1,2) = s(a,1,1) = a^1 = a. In the same way, s(a,1,c) = s(a,1,1) = a for any c.

Next, s(a,b,2) = s(a, s(a,b-1,2) ,1) = a^s(a,b-1,2) = a^(a^s(a,b-2,2)) = … = a^a^…a^s(a,1,2) (with b-1 ^′s) = a^a^…a^a with b a′s, so it’s exactly tetration – s(a,b,2) = a^^b.

Next, s(a,b,3) = s(a, s(a,b-1,3) ,2) = a^^s(a,b-1,3) = a^^(a^^s(a,b-2,3)) = … = a^^a^^…a^^s(a,1,3) (with b-1 ^^′s) = a^^a^^…a^^a with b a′s, so it’s exactly pentation – s(a,b,3) = a^^^b.

And so on, s(a,b,c) = a^^…^^b (with c ^′s), so the 3-entry arrays are equivalent to Knuth’s up-arrow notation.

4-entry arrays

s(a,b,c,1) = s(a,b,c), applying rule 3. And in the same way, s(a,1,c,d) = s(a,1,1,d). This hold for more entries – s(a,1,c #) = s(a,1,1 #) where # is a part of array.

Now look at s(a,b,1,2). Here we need to start the process. First we look at the 3rd entry – it’s 1, so we meet case A. Then look at the next entry (the 4th entry) – it’s 2, so we meet case B. Change the “1,2” into “b,1”, and then change “the entries before them” (i.e. first 2 entries) into the base a. So s(a,b,1,2) = s(a,a,b,1) = s(a,a,b) = a^^…^^a with b ^′s. Especially, s(a,1,c,2) = s(a,1,1,2) = a^a.

Then s(a,b,2,2) = s(a, s(a,b-1,2,2) ,1,2) = … = s(a, s(a, … s(a, s(a,1,2,2) ,1,2) … ,1,2) ,1,2) (with b-1 “1,2”′s) = s(a, s(a, … s(a,a^a,1,2) … ,1,2) ,1,2) (with b-1 2′s). And s(a,b,c,2) = s(a, s(a, … s(a,a^a,c-1,2) … ,c-1,2) ,c-1,2) (with b-1 2′s).

Now look at s(a,b,1,3). In the same way, s(a,b,1,3) = s(a,a,b,2), and s(a,1,c,3) = s(a,1,1,3) = s(a,a,1,2) = a^^…^^a with a ^′s. s(a,b,1,c) = s(a,a,b,c-1), and s(a,1,c,d) = s(a,1,1,d) = s(a,a,1,d-1) = s(a,a,a,d-2).

It turns out that 4-entry arrays are equivalent to the full Conway’s chained arrow notation. More detailed, s(a,b,c,d) = {\underbrace{a\rightarrow a\rightarrow\cdots a\rightarrow a}_{d}\rightarrow b\rightarrow c}.

The process

Comparing to rule 1~3, the process seems complex, so let me explain a little more.

First, from the 3rd entry on, we search for the first non-1 entry – it can be the 3rd entry, the 4th entry, the 5th entry and so on. The entry immediately before it must be 1, even for the 2nd entry, because if neither 2nd nor 3rd entry is 1 then it fits rule 3. Then, the array s(@ 1,n #) = s(@’ b,n-1 #) where every entry in @’ is base a and the # stays the same.

So for example, s(a,1,c #) = s(a,1,c-1 #) (the iterator is 1)= s(a,1,c-2 #) = … = s(a,1,1 #),

s(a,b,1,c #) = s(a,a,b,c-1 #)
s(a,b,1,1,c #) = s(a,a,a,b,c-1 #)
s(a,b,1,1,1,c #) = s(a,a,a,a,b,c-1 #)

and so on.

Comparison

There’re many other notations to express large numbers, with different strength. One of them is fast-growing hierarchy (FGH), which maps ordinals into functions. It’s used as a general method to compare strength of different notations. FGH is defined as follows:

{f_0(n)=n+1}
{f_{\alpha+1}(n)=f_\alpha^n(n)}
{f_\alpha(n)=f_{\alpha[n]}(n)} when α is a limit ordinal

where α[n] means the element n of fundamental sequence of limit ordinal α.

Only ordinals themselves are not enough for definition of FGH. We have to define fundamental sequences of every limit ordinals, or FGH stops here. For Cantor’s normal form, the fundamental sequences are defined as follows: ({\alpha_1\geq\alpha_2\geq\cdots\alpha_{k-1}\geq\alpha_k})

 {(\omega^{\alpha_1}+\omega^{\alpha_2}+\cdots\omega^{\alpha_{k-1}}+\omega^{\alpha_k})[n]=\omega^{\alpha_1}+\omega^{\alpha_2}+\cdots\omega^{\alpha_{k-1}}+(\omega^{\alpha_k}[n])}
{\omega^1[n]=n}
{\omega^{\alpha+1}[n]=\omega^\alpha\times n}
{\omega^\alpha[n]=\omega^{\alpha[n]}} when α is a limit ordinal

And we say function a(n) has growth rate α if a(n) is comparable to {f_\alpha(n)}, or a(n) eventually outgrows any {f_\beta(n)} for all β < α but {f_\alpha(n)} eventually outgrows a(n) for limit α.

From “3-entry arrays” we know that s(n,n,1,2) = s(n,n,n) has growth rate ω, which eventually outgrows all functions provably recursive in recursive comprehension (RCA0), weak König’s lemma (WKL0), primitive recursive arithmetic (PRA) and arithmetic with induction on Σ1-predicates (IΣ1). And it’s comparable to those functions:

Then

s(n,n,2,2) has growth rate ω+1, comparable to exploding tree function
s(n,n,3,2) has growth rate ω+2
s(n,n,4,2) has growth rate ω+3
s(n,n,1,3) = s(n,n,n,2) has growth rate ω2
s(n,n,2,3) has growth rate ω2+1
s(n,n,3,3) has growth rate ω2+2
s(n,n,1,4) has growth rate ω3
s(n,n,1,5) has growth rate ω4
s(n,n,a,b) has growth rate ω(b-1)+(a-1)
s(n,n,1,1,2) = s(n,n,n,n) has growth rate {\omega^2}, reaching the limit of Conway’s chained arrow notation
s(n,n,2,1,2) has growth rate {\omega^2+1}
s(n,n,3,1,2) has growth rate {\omega^2+2}
s(n,n,1,2,2) has growth rate {\omega^2+\omega}
s(n,n,2,2,2) has growth rate {\omega^2+\omega+1}
s(n,n,1,3,2) has growth rate {\omega^2+\omega2}
s(n,n,1,4,2) has growth rate {\omega^2+\omega3}
s(n,n,1,1,3) = s(n,n,n,n,2) has growth rate {\omega^22}
s(n,n,2,1,3) has growth rate {\omega^22+1}
s(n,n,1,2,3) has growth rate {\omega^22+\omega}
s(n,n,1,1,4) has growth rate {\omega^23}
s(n,n,1,1,5) has growth rate {\omega^24}
s(n,n,a,b,c) has growth rate {\omega^2(c-1)+\omega(b-1)+(a-1)}
s(n,n,1,1,1,2) = s(n,n,n,n,n) has growth rate {\omega^3}
s(n,n,2,1,1,2) has growth rate {\omega^3+1}
s(n,n,1,2,1,2) has growth rate {\omega^3+\omega}
s(n,n,1,1,2,2) has growth rate {\omega^3+\omega^2}
s(n,n,1,1,3,2) has growth rate {\omega^3+\omega^22}
s(n,n,1,1,1,3) has growth rate {\omega^32}
s(n,n,1,1,1,4) has growth rate {\omega^33}
s(n,n,a,b,c,d) has growth rate {\omega^3(d-1)+\omega^2(c-1)+\omega(b-1)+(a-1)}
s(n,n,1,1,1,1,2) has growth rate {\omega^4}
s(n,n,1,1,1,1,1,2) has growth rate {\omega^5}
s(n,n,…,n,n) with m entries has growth rate {\omega^{m-2}}

Function f(n) = s(n,n,…,n,n) with n entries eventually outgrows any expression in LAN with constant amount of entries, so it has growth rate {\omega^\omega}. That’s the limit of the LAN, and it’s comparable to those functions:

6 thoughts on “Linear array notation”

    • All the arrays follow two types of rules. One is “the rule 1 ~ 3”, and the other is “the process”, which starts when none of the rules apply. So, if one rule of those 3 rules apply, then the process doesn’t start.

      For s(a,b,2,2), if b > 1, then it match rule 3. So rule 3 applies and s(a,b,2,2) = s(a,s(a,b-1,2,2),1,2) – that’s one step in solving the expression.

      Like

      Reply
  3. Pingback: Linear array notation – Integral View

.