Extended array notation

Prev: Linear array notation    Next: Expanding array notation

Extended array notation (exAN) is the second part of my array notation.

Definition

First, we need more things to express the notation, mainly separators and layers.

Something

Symbol { is called lbrace, with ASCII = 123 and LaTeX = \{ or \lbrace
Symbol } is called rbrace, with ASCII = 125 and LaTeX = \} or \rbrace

{m1A1m2A2…mk-1Ak-1mk} is a separator, where mi′s are positive integers, Ai′s are separators and k ≥ 1.

In the definition of separators, if k=1, then there’s no Si, so {m} where m is a positive integer is a separator. The simplest separator is {1}, and the comma is just a shorthand for it.

Entries are positive integers separated by separators. Note that there’re entries in arrays, and there’re entries also in separators!

Here’s the definition of layer:

  • In array s(m1A1m2A2…mk-1Ak-1mk), all entry mi′s are at base layer, and all separator Ai′s are at layer 1.
  • If separator {m1A1m2A2…mk-1Ak-1mk} is at layer n, then all separator Ai′s are at layer n+1.

A more formal definition of separators is:

  • {m} is a separator, where m is a positive integer.
  • {#Am} is a separator, where m is a positive integer, A is a separator, and # is a string such that {#} is a separator.

And a more formal definition of array is:

  • s(a,b) is an array, where a and b are positive integers.
  • s(#Am) is an array, where m is a positive integer, A is a separator, and # is a string such that s(#) is an array.

Rules and process

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

where # is a string of entries and separators, it can also be empty. A is a separator.

If none of the 3 rules above applies, start the process shown below. Note that case B1 and B3 are terminal but case A and B2 are 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 n is not 1, look to your left:
    • Case B1: If the comma is immediately before you, 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 at base layer before them into the base.
      3. The process ends.
    • Case B2: If a separator not comma A is immediately before you, then
      1. Change the “A n” into “A 2 A n-1”
      2. Jump to the first entry of the former A.
    • Case B3: If an lbrace is immediately before you, then
      1. Change separator {n #} into string Sb, where b is the iterator, S1 = “{n-1 #}” and Si+1 = “Si b {n-1 #}”.
      2. The process ends.

Explanation

Rule 1 and 3, and case A are the same as the rules in LAN. Case B1 is a little different, but rule 2b, case B2 and B3 are all new rules.

Dimensional arrays

Dimensional arrays are arrays with separators up to {n} in exAN. Here rule B2 and B3 show their strength.

s(a,b{2}2) is the simplest dimensional array. To solve it, we need to use the process. The 3rd entry is 2, and there’s a separator not comma {2} immediately before the 2, so we meet case B2. Now change the array into s(a,b{2}2{2}1), then restart the process from the first entry in the former {2}. It’s 2 not 1, and an lbrace is immediately before the 2, so we meet case B3. Now change the {2} into {1}b{1}b…{1}b{1} with b {1}’s, so s(a,b{2}2) = s(a,b{1}b{1}b…{1}b{1}2{2}1) (with b {1}’s)= s(a,b,b,b…,b,2) with b b’s (apply rule 2, and note that {1} is the comma).

Unlike BEAF and BAN, in this array notation, s(a,b{2}2), s(a,b,1{2}2) and s(a,b,1,1{2}2) are not the same. They’re s(a,b,b,b…,b,2), s(a,b,1,b,b…,b,2) and s(a,b,1,1,b,b…,b,2) (with b b’s) respectively.

s(a,b{2}3) = s(a,b,b,b…,b,2{2}2) with b b’s, when it reduces to s(a,b’,1,1…,1,1{2}2) , it becomes s(a,b’,1,1,…1,1,b’,b’…,b’,b’,2) with b’ b’′s. At most situations, b is nothing comparing to b’, so the remaining entries (the b 1’s remaining in s(a,b’,1,1…,1,1{2}2)) don’t affect the strength of the notation.

Some more examples,

s(a,b{2}1{2}2) = s(a,b{2}1,b…,b,2) (with b b’s)= s(a,a{2}b,b-1,b,…b,2) (with b+1 entries after the {2})
s(a,b{2}1{2}c) = s(a,b{2}1,b…,b,2{2}c-1) (with b+1 entries between two {2}′s)
s(a,b{c}d) = s(a,b{c-1}b{c-1}b…{c-1}b{c-1}2{c}d-1) (with b {c-1}’s)

Rule 2b and case B1

This two rules allow us to go further.

For example, to solve s(a,b{1,2}2), we start the process, and meet case B2, then the array becomes s(a,b{1,2}2{1,2}1). Then we restart the process from the 1 in the former {1,2}, and meet case B1, so change the “1,2” into “b,1”, and change the entries at base layer into a. So s(a,b{1,2}2) = s(a,a{b,1}2{1,2}1). Now rule 2a applies, so s(a,a{b,1}2{1,2}1) = s(a,a{b,1}2), then rule 2b applies, so s(a,a{b,1}2) = s(a,a{b}2). As a result, we can have more than 1 entries inside a separator.

To solve s(a,b{1{2}1,2}2), we start the process, then meet case B2, then meet case B1. Before case B1 applies, the array is s(a,b{1{2}1,2}2{1{2}1,2}1); after case B1 applies, the array becomes s(a,a{1{2}b,1}2{1{2}1,2}1). Then rule 2a and 2b applies, so s(a,b{1{2}1,2}2) = s(a,a{1{2}b}2). What if we use the case B1 in Linear array notation? s(a,b{1{2}1,2}2) will be s(a,a{a{a}b}2). When a ≥ 3 and b ≥ 2, it’ll reduces to something containing {1{2}1,2} again – it can never be solved. So a change on case B1 is necessary.

Comparison

Here’re some comparisons between exAN and FGH (growth rate).

s(n,n{2}2) has growth rate {\omega^\omega}
s(n,n,2{2}2) has growth rate {\omega^\omega+1}
s(n,n,3{2}2) has growth rate {\omega^\omega+2}
s(n,n,1,2{2}2) has growth rate {\omega^\omega+\omega}
s(n,n,2,2{2}2) has growth rate {\omega^\omega+\omega+1}
s(n,n,1,3{2}2) has growth rate {\omega^\omega+\omega2}
s(n,n,1,4{2}2) has growth rate {\omega^\omega+\omega3}
s(n,n,1,1,2{2}2) has growth rate {\omega^\omega+\omega^2}
s(n,n,2,1,2{2}2) has growth rate {\omega^\omega+\omega^2+1}
s(n,n,1,2,2{2}2) has growth rate {\omega^\omega+\omega^2+\omega}
s(n,n,1,1,3{2}2) has growth rate {\omega^\omega+\omega^22}
s(n,n,1,1,1,2{2}2) has growth rate {\omega^\omega+\omega^3}
s(n,n,1,1…,1,2{2}2) with m 1’s has growth rate {\omega^\omega+\omega^m}
s(n,n{2}3) has growth rate {\omega^\omega2}
s(n,n,2{2}3) has growth rate {\omega^\omega2+1}
s(n,n,1,2{2}3) has growth rate {\omega^\omega2+\omega}
s(n,n,1,1,2{2}3) has growth rate {\omega^\omega2+\omega^2}
s(n,n,1,1,1,2{2}3) has growth rate {\omega^\omega2+\omega^3}
s(n,n{2}4) has growth rate {\omega^\omega3}
s(n,n{2}1,2) = s(n,n{2}n) has growth rate {\omega^{\omega+1}}
s(n,n,2{2}1,2) has growth rate {\omega^{\omega+1}+1}
s(n,n,1,2{2}1,2) has growth rate {\omega^{\omega+1}+\omega}
s(n,n{2}2,2) has growth rate {\omega^{\omega+1}+\omega^\omega}
s(n,n{2}3,2) has growth rate {\omega^{\omega+1}+\omega^\omega2}
s(n,n{2}1,3) has growth rate {\omega^{\omega+1}2}
s(n,n{2}1,4) has growth rate {\omega^{\omega+1}3}
s(n,n{2}1,1,2) has growth rate {\omega^{\omega+2}}
s(n,n{2}2,1,2) has growth rate {\omega^{\omega+2}+\omega^\omega}
s(n,n{2}1,2,2) has growth rate {\omega^{\omega+2}+\omega^{\omega+1}}
s(n,n{2}1,1,3) has growth rate {\omega^{\omega+2}2}
s(n,n{2}1,1,1,2) has growth rate {\omega^{\omega+3}}
s(n,n{2}1,1,1,1,2) has growth rate {\omega^{\omega+4}}
s(n,n{2}1{2}2) has growth rate {\omega^{\omega2}}
s(n,n,2{2}1{2}2) has growth rate {\omega^{\omega2}+1}
s(n,n{2}2{2}2) has growth rate {\omega^{\omega2}+\omega^\omega}
s(n,n{2}1,2{2}2) has growth rate {\omega^{\omega2}+\omega^{\omega+1}}
s(n,n{2}1,1,2{2}2) has growth rate {\omega^{\omega2}+\omega^{\omega+2}}
s(n,n{2}1{2}3) has growth rate {\omega^{\omega2}2}
s(n,n{2}1{2}1,2) has growth rate {\omega^{\omega2+1}}
s(n,n{2}1{2}1,1,2) has growth rate {\omega^{\omega2+2}}
s(n,n{2}1{2}1{2}2) has growth rate {\omega^{\omega3}}
s(n,n{2}1{2}1{2}1{2}2) has growth rate {\omega^{\omega4}}
s(n,n{3}2) has growth rate {\omega^{\omega^2}}
s(n,n,2{3}2) has growth rate {\omega^{\omega^2}+1}
s(n,n{2}2{3}2) has growth rate {\omega^{\omega^2}+\omega^\omega}
s(n,n{2}1,2{3}2) has growth rate {\omega^{\omega^2}+\omega^{\omega+1}}
s(n,n{2}1{2}2{3}2) has growth rate {\omega^{\omega^2}+\omega^{\omega2}}
s(n,n{2}1{2}1{2}2{3}2) has growth rate {\omega^{\omega^2}+\omega^{\omega3}}
s(n,n{3}3) has growth rate {\omega^{\omega^2}2}
s(n,n{3}1,2) has growth rate {\omega^{\omega^2+1}}
s(n,n{3}1{2}2) has growth rate {\omega^{\omega^2+\omega}}
s(n,n{3}1{2}1{2}2) has growth rate {\omega^{\omega^2+\omega2}}
s(n,n{3}1{3}2) has growth rate {\omega^{\omega^22}}
s(n,n{3}1{3}1{3}2) has growth rate {\omega^{\omega^23}}
s(n,n{4}2) has growth rate {\omega^{\omega^3}}
s(n,n{5}2) has growth rate {\omega^{\omega^4}}
s(n,n{1,2}2) has growth rate {\omega^{\omega^\omega}}, also the limit of dimensional arrays in BEAF and BAN
s(n,n,2{1,2}2) has growth rate {\omega^{\omega^\omega}+1}
s(n,n{2}2{1,2}2) has growth rate {\omega^{\omega^\omega}+\omega^\omega}
s(n,n{3}2{1,2}2) has growth rate {\omega^{\omega^\omega}+\omega^{\omega^2}}
s(n,n{4}2{1,2}2) has growth rate {\omega^{\omega^\omega}+\omega^{\omega^3}}
s(n,n{1,2}3) has growth rate {\omega^{\omega^\omega}2}
s(n,n{1,2}1,2) has growth rate {\omega^{\omega^\omega+1}}
s(n,n{1,2}1{2}2) has growth rate {\omega^{\omega^\omega+\omega}}
s(n,n{1,2}1{3}2) has growth rate {\omega^{\omega^\omega+\omega^2}}
s(n,n{1,2}1{4}2) has growth rate {\omega^{\omega^\omega+\omega^3}}
s(n,n{1,2}1{1,2}2) has growth rate {\omega^{\omega^\omega2}}
s(n,n{1,2}1{1,2}1{1,2}2) has growth rate {\omega^{\omega^\omega3}}
s(n,n{2,2}2) has growth rate {\omega^{\omega^{\omega+1}}}
s(n,n{2,2}3) has growth rate {\omega^{\omega^{\omega+1}}2}
s(n,n{2,2}1,2) has growth rate {\omega^{\omega^{\omega+1}+1}}
s(n,n{2,2}1{1,2}2) has growth rate {\omega^{\omega^{\omega+1}+\omega^\omega}}
s(n,n{2,2}1{1,2}1{1,2}2) has growth rate {\omega^{\omega^{\omega+1}+\omega^\omega2}}
s(n,n{2,2}1{2,2}2) has growth rate {\omega^{\omega^{\omega+1}2}}
s(n,n{2,2}1{2,2}1{2,2}2) has growth rate {\omega^{\omega^{\omega+1}3}}
s(n,n{3,2}2) has growth rate {\omega^{\omega^{\omega+2}}}
s(n,n{3,2}1{3,2}2) has growth rate {\omega^{\omega^{\omega+2}2}}
s(n,n{4,2}2) has growth rate {\omega^{\omega^{\omega+3}}}
s(n,n{1,3}2) has growth rate {\omega^{\omega^{\omega2}}}
s(n,n{2,3}2) has growth rate {\omega^{\omega^{\omega2+1}}}
s(n,n{3,3}2) has growth rate {\omega^{\omega^{\omega2+2}}}
s(n,n{1,4}2) has growth rate {\omega^{\omega^{\omega3}}}
s(n,n{1,1,2}2) has growth rate {\omega^{\omega^{\omega^2}}}
s(n,n{1,1,2}3) has growth rate {\omega^{\omega^{\omega^2}}2}
s(n,n{1,1,2}1,2) has growth rate {\omega^{\omega^{\omega^2}+1}}
s(n,n{1,1,2}1{1,1,2}2) has growth rate {\omega^{\omega^{\omega^2}2}}
s(n,n{2,1,2}2) has growth rate {\omega^{\omega^{\omega^2+1}}}
s(n,n{1,2,2}2) has growth rate {\omega^{\omega^{\omega^2+\omega}}}
s(n,n{1,1,3}2) has growth rate {\omega^{\omega^{\omega^22}}}
s(n,n{1,1,1,2}2) has growth rate {\omega^{\omega^{\omega^3}}}
s(n,n{1{2}2}2) has growth rate {\omega^{\omega^{\omega^\omega}}}, also the limit of hyper-dimensional array notation in BAN
s(n,n{1{2}2}3) has growth rate {\omega^{\omega^{\omega^\omega}}2}
s(n,n{1{2}2}1{1{2}2}2) has growth rate {\omega^{\omega^{\omega^\omega}+1}}
s(n,n{2{2}2}2) has growth rate {\omega^{\omega^{\omega^\omega}2}}
s(n,n{1,2{2}2}2) has growth rate {\omega^{\omega^{\omega^\omega+1}}}
s(n,n{1{2}3}2) has growth rate {\omega^{\omega^{\omega^\omega2}}}
s(n,n{1{2}1,2}2) has growth rate {\omega^{\omega^{\omega^{\omega+1}}}}
s(n,n{1{2}1{2}2}2) has growth rate {\omega^{\omega^{\omega^{\omega2}}}}
s(n,n{1{3}2}2) has growth rate {\omega^{\omega^{\omega^{\omega^2}}}}
s(n,n{1{4}2}2) has growth rate {\omega^{\omega^{\omega^{\omega^3}}}}
s(n,n{1{1,2}2}2) has growth rate {\omega^{\omega^{\omega^{\omega^\omega}}}}
s(n,n{1{1{2}2}2}2) has growth rate {\omega^{\omega^{\omega^{\omega^{\omega^\omega}}}}}
s(n,n{1{1{1,2}2}2}2) has growth rate {\omega^{\omega^{\omega^{\omega^{\omega^{\omega^\omega}}}}}}

Function f(n) = s(n,n{1{1…{1{1,2}2}…2}2}2) (with n 2’s) eventually outgrows any expression in exAN, so it has growth rate {\varepsilon_0}. That’s the limit of exAN, also eventually outgrows any function provable recursive in Peano arithmetic (PA) and arithmetical comprehension (ACA0). And it has similar growth rate to these functions:

Advertisements

2 thoughts on “Extended array notation

.

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s