Fandom

Googology Wiki

Array notation

10,540pages on
this wiki
Add New Page
Talk16 Share
For the extended function that allows multidimensional/superdimensional arrays, see BEAF.

Array notation is a googological function created by Jonathan Bowers.[1] It was generalized to Extended Array Notation and eventually BEAF and BAN.

It is not to be confused with other array notations, such as Hyperfactorial array notation, Bird's array notation, Graham Array Notation, Saibian's array notation, Strong array notation etc.

History Edit

Bowers say he was inspired to explore googology by reading a book that discussed hyper operators. From them he developed the four-argument extended operators, which are as strong as chained arrow notation. Later, Bowers decided to extend his operators to far more arguments than four, leading to the invention of array notation.[1]

Initially Rule 1 had \(\{a, b\} = a + b\). At Chris Bird's suggestion, he changed this to \(a^b\) so that Rules 1 and 2 would be compatible.

Bowers usually used angle brackets <> for delimiters of arrays, but the notation that originally appeared on the site used curly braces {} instead, due to angle brackets causing problems with HTML. Aware of this fact, Sbiis Saibian uses curly braces for the original \(a + b\) array notation, and angle brackets for the revised \(a^b\) array notation.[2]

As a convention, the rest of this article will use curly braces for the new array notation.

Nathan Ho and Wojowu showed that array notation terminates — that is, its output exists for all input sequences.[3]

Rules Edit

An array is defined as a finite sequence of positive integers. Array notation is a function \(v(A)\) mapping these sequences to large positive integers. If \(A = (a_1, a_2, \ldots, a_n)\), we write \(\{a_1, a_2, \ldots, a_n\}\) as a shorthand for \(v(A)\).

  1. \(\{a\} = a\) and \(\{a,b\} = a^b\)
  2. \(\{a,b,c,\ldots,n,1\} = \{a,b,c,\ldots,n\}\)
  3. \(\{a,1,b,c,\ldots,n\} = a\)
  4. \(\{a,b,1,\ldots,1,c,d,\ldots,n\} = \{a,a,a,\ldots,\{a,b-1,1,\ldots,1,c,d,\ldots,n\},c-1,d,\ldots,n\}\). In other words, if the third element is 1, then:
    • all elements before the next non-1 element become the first element,
    • the last of the above becomes the original array with the second element decreased by 1, and
    • the said non-1 element is decreased by one.
  5. If rules 1 to 4 do not apply, \(\{a,b,c,d,\ldots,n\} = \{a,\{a,b-1,c,d,\ldots,n\},c-1,d,\ldots,n\}\)

Extended Operators Edit

Bowers also invented a set of "extended" operators to complement Array Notation.

\[a \{c\} b = \{a,b,c\}\]

For example, \(3\{3\}3 = \{3,3,3\}\) = tritri.

In the array {a,b,c,d,e,f,g,h}, a, b, and c are all shown in numeric form, with d sets of curly braces { }. To represent e, Bowers uses e - 1 sets of square brackets [ ] above and below the sentence, f is represented with f - 1 Saturn-like rings around the sentence, and g is represented by g - 1 sets of X-wing brackets around it. h is represented with square plates with opposite edges bent 90 degrees inwards (i.e. 3-dimensional versions of square brackets).[1][2]

Types of linear arrays Edit

Below 3 entriesEdit

When there are less then 3 entries, the arrays are fairly trivial to solve.

  • The simplest array of all is the empty one: \(\{\} = 1\). This is technically not a valid operation (it is in BEAF), but it is consistent with the rest of the rules.
  • Arrays of size 1: \(\{a\} = a\) (not to be confused with the bracket operator).
  • Arrays of size 2: \(\{a,b\} = a^b\), which is a to the power of b (addition on the old version).

3 to 4 entries Edit

Arrays of size 3 gives the same value with chained arrow notation: \(\{a,b,c\} = a \rightarrow b \rightarrow c\), just like arrays of size 1 and 2.

The 4 entry arrays, \(\{a,b,c,d\}\), does not continue with this pattern; in fact, according to Bird's Proof, \(\{a,b,c,d\}\) surpasses a length d+2 chain with the same numbers in chained-arrow notation.

Approximations in other notations Edit

\(\lbrace n,a+1,b+1,c+1,d+1,... \rbrace\) is approximated as follows.

Notation Approximation
Multivariable Ackermann \(f^a(n); f(n)=A(...,d,c,b,n)\)
Fast-growing hierarchy \(f_{... + \omega^2 d + \omega c + b}^{a}(n)\)
Hardy hierarchy \(H_{\omega^{... + \omega^2 d + \omega c + b} a}(n)\)

Turing machine code Edit

Input format: x|A| where A is array in form of strings of 1's divided by blanks. For example, x|111 111 111| calculates tritri.

Turing machine code

0 * * r 0
0 _ _ r 1
0 | | r 0'
0' * * r 0'
0' _ _ r 1
0' | _ l h0
1 _ _ r 1
1 1 1 r 2
2 _ _ r 3
2 | _ l 4
2 1 1 r 5
3 * _ r 3
3 | _ l 4
4 * * l 4
4 1 _ l r0
5 1 1 r 5
5 | _ l 6
5 _ _ r 9
6 1 x l 7
6 _ 1 l s1
7 * * l 7
7 | | r 8
7 x x r 8
8 1 x r s0
8 _ 1 r s3
9 1 1 r 10
9 _ _ r 9
9 y y l b0
10 1 1 r 11
10 _ _ r 9
10 | _ l 12
11 1 1 r 11
11 _ _ r 9
11 | | l 15
12 1 _ l 13
13 _ | l 14
14 * * l 14
14 | | r 0
15 * * l 15
15 | | r c0
15 x x r c0
15 y y r c0

c0 1 x r c1
c0 _ y r c3
c0 | | r c6
c1 * * r c1
c1 | | r c2
c2 * * r c2
c2 _ x l c5
c3 * * r c3
c3 | | r c4
c4 * * r c4
c4 _ y l c5
c5 * * l c5
c5 | | l 15
c6 x 1 r c6
c6 y _ r c6
c6 _ | l 16

16 * * l 16
16 | | r 17
17 1 1 r 17
17 _ _ r 18
18 1 1 r 18
18 _ 1 l 19
18 | _ l 20
19 1 _ r 18
20 1 | l 21
21 * * l 21
21 | | l 22
22 x 1 l 22
22 y _ l 22
22 | | r 23

23 1 1 r 23
23 _ _ r 24
24 1 1 r 24
24 _ _ r 25
25 1 y r 26
26 1 1 l 27
26 _ _ r 25
27 y _ l 27
27 _ _ l 28
28 1 1 l 28
28 y y l 27
28 _ _ r 29
29 1 x r 30
30 * * r 30
30 | | r 0

r0 _ _ l r0
r0 1 _ l r1
r0 | _ l r7
r1 * * l r1
r1 x 1 r r2
r2 1 x r r3
r2 _ x r r5
r2 | | r h0
r3 * * r r3
r3 | | r r4
r4 1 1 r r4
r4 _ _ l r0
r5 _ _ r r6
r5 1 _ r r10
r5 y _ r r13
r6 * * r r6
r6 | | r r4
r7 1 | l r8
r8 1 1 l r8
r8 _ 1 l r9
r8 x x r 32
r9 1 _ l r8
r9 _ _ l r9
r9 y _ l r14
r9 x _ r r9'
r9' _ _ l 31
r9' * * l 14
r10 _ 1 r r11
r10 1 1 r r10
r10 | 1 r r12
r11 _ _ r r11
r11 1 _ r r10
r12 _ _ l r7
r12 1 | l r1
r13 _ y r r5
r14 _ y l r9

b0 * * l b0
b0 | | r b0'
b0' 1 x r b0
b0 x 1 r b1
b1 _ _ r b7
b1 1 x r b2
b2 * * r b2
b2 y 1 r b3
b3 _ y r b4
b4 y _ r b3
b4 1 _ r b5
b5 1 1 r b5
b5 _ 1 r b4
b5 | 1 r b6
b6 _ | l b0
b7 * * r b7
b7 y 1 r 9

h0 * * l h0
h0 | 1 l h1
h1 * _ r halt

s0 * * r s0
s0 x x l 6
s1 * * l s1
s1 x x r s2
s2 1 _ r s4
s3 1 1 r s3
s3 x _ r s4
s4 * 1 r s4
s4 _ _ l s5
s5 * * l s5
s5 x 1 l s5
s5 | | r p0

p0 1 1 l p0a
p0 _ _ r p19
p0a | | r p0b
p0b 1 _ r p1
p1 1 _ r p21
p1 _ _ r p10
p1 x _ r p11
p2 * * r p2
p2 _ _ r p3
p3 1 _ r p4
p3 x _ l p8
p4 1 1 r p4
p4 _ x r p5
p4 x x r p5
p5 1 1 r p5
p5 _ 1 l p6
p6 1 1 l p6
p6 * * l p7
p7 1 1 l p7
p7 _ 1 r p3
p8 1 1 l p8
p8 x x l p8
p8 _ x l p9
p9 1 1 l p8
p9 _ _ r p10
p10 x _ r p1
p10 1 1 l p20
p11 1 1 r p11
p11 x _ r p11
p11 _ _ l p12
p12 1 1 l p12
p12 _ _ r m0
m0 1 _ r m1
m0 _ _ r m9
m1 1 1 r m1
m1 _ _ r m2
m2 1 _ r m3
m2 _ _ l m7
m3 1 1 r m3
m3 _ _ r m4
m4 1 1 r m4
m4 _ 1 l m5
m5 1 1 l m5
m5 _ _ l m6
m6 1 1 l m6
m6 _ 1 r m2
m7 1 1 l m7
m7 _ _ l m8
m8 1 1 l m8
m8 _ _ r m0
m9 1 _ r m9
m9 _ 1 r p13
p13 1 1 r p13
p13 _ _ l p14
p14 1 _ l p15
p15 1 1 l p15
p15 _ 1 l p16
p16 1 1 r p17
p16 _ _ r p13
p16 x _ r p18
p16 | | r p22
p17 1 _ l p12
p18 1 _ r halt
p19 1 _ r p19
p19 _ 1 r halt
p20 * * l p20
p20 x _ r halt
p21 * * r p2
p21 _ x r p3
p22 1 1 r p22
p22 _ _ l p23
p23 1 _ l r0

31 _ x r 32
32 * * r 32
32 | _ l r7

Sources Edit

  1. 1.0 1.1 1.2 Bowers, Jonathan. Exploding Array Function. Retrieved 2013-11-26.
  2. 2.0 2.1 Saibian, Sbiis. 4.1.2 - Jonathan Bowers' Extended Operator Notation. Retrieved 2013-11-26.
  3. http://snappizz.com/termination

See also Edit

Main article: Jonathan Bowers
Works: Array notation · Extended Array Notation · BEAF · Forever Endeavor
External link: Personal website

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.