Og Arrays

$ 1. Og's big numbers My new array system 'Og' for big numbers is called after a little box of Zombie OG that was left behind on the stairs. A growers' website says that OG could mean "Ocean Grown" or "Original Gangster". Anyway, there is an ocean of big numbers for the mathematician to explore. $ 1.1. Constructing the first row Numbers are basically expressed as integers 1.. in unary notation. This makes sense for power towers a^^3 and larger. We use decimal base as shorthand. The rules can match a whole = expression, or select forms in the expression, while scanning `= from the left, or back =` from the right side. A tick `  space placeholder is used in the rule, to skip over a passive unchanged part in the expression. Define rewrite rules for the 'Og' array row. -Og.1 (a,b) = ab -Og.2 ,1) =` ) -Og.3 a,b` 1?,1p `= a,` ab,p Rules have greedy variables, so that whole numbers are selected. An option ? after a sign is not greedy, so it won't take 1 from b here, but it will on the row. Sum variable b≥0 can be zero 0 or empty   after upload with rule '3.' or in the input expression, but the iterator p>0 must be a positive number. For example, the input expression (2,3,2) is by rule '3.' reduced to (2,5,1) then only rule '2.' applies (2,5) and then rule '1.' will evaluate to number 7 as output, which is 1111111 in unary notation. Another way to express this is by 3+2*2 old school operations, or with our newly defined 2*2\3 backstars. Express superpower numbers with just two rules in 'Bs' for optional "backstar" operations. We can select strictly =` first match from the right, or give rule '1.' priority. -Bs.1 a*{c1}1\? =` a -Bs.2 a*{c1}b1\? =` a*{c1}b\*{c}a Explain the regex notation: a quantifier to count {c stars to 0} and an option ? sign for a right backslash \ that is erased in the evaluation. The empty star in \*{c=0} just postpones + addition of unary numbers. Superstars are the same operators as Knuth's up-arrows, but with one * sign more, so that a*{k1}p equals a^{k>0}p with carets. An evaluation example with backstars, simplified := to backcarets. We show the applied 'rtl' rule numbers on the equal sign. 3***2 := 3^^2 =2 3^^1\^3 =1 3^3 =2 3^2\*3 =2 3^1\*3*3 =1 3*3*3 =2 3*3*2\3 =2 3*3*1\6 =1 3*9 =2 3*8\3 == 3*1\24 =1 27. Multiply in 'Og' by iterator c which repeats addition. Leave away array brackets, and indicate 'ltr' rule numbers a,b,1 2= a,b 1= ab a,b,2 3= a,ab,1 = aab a,b,c1 = a,ab,c == a,a*c+b,1 :c = a*c1\b Iteration over d repeatedly substitutes a multiplication rest c=1 for the sum ab which works out to exponentiation. a,b,c1,2 3= a,ab,c,2 == a,a*c+b,1,2 3,2= a,,a*c1\b = a*a*c1\b a,b,c,d1 = a,,a*c\b,d == a,,.a*..c\b :d = a^d1\*c\b The 'rep' :d is to repeatedly write the . selected part a* left of the dots .. in the expression. Work out a row of five in 'Og' to a tower of ^ exponents, notated with the superoperator ^^ of "tetration". a,b,c,d,e1 = a,,1,a^d\*c\b,e == a,,1,.a^..d\*c\b :e = a^^e1\^d\*c\b Continue like this for the formula that equates the whole 'Og' array row with backstar operations. a,b.,p_i.. 1:k = a.*{i}p_i\..b k:1 Repeat the selections with vars p_i>0 some k≥0 times, and increment or decrement index i for each, as indicated in the 'rep'. When sum b is \0 and for i<k we append \*{i}1 identities, then a*{k}p_k is a plain superpower, as in this equation. a,.,1..p :k>0 = a*{k}p1 By definition with 1? in 'Og' the reload value for empty ,0 slots will be the same as for ,1 entries. So we can simplify our superpower array further, with commas that take the role of a countable superpower ,{k} starting from ,{1} addition, the empty *{0} star operator. a,{k1}p = a*{k}p For example, we can express "pentation" with a row of five commas in 'Og'. a1,,,,,f2 = a1,,,,a1,f1 == a1,a1,a,a,a,f1 = a1,,1,1,a1^^a1,f == a1,,1,1,.a1^^..a1 :f = a1^^^f2 By formula the left part a1,a1,a,a,a on line two equals the backstar equation a1***a\**a\*a\a1 which we backtrack to upload a1^^a1 in line three. The superpower of pentation repeats tetrations, to evaluate 'rtl' or top down. This produces numbers that are larger than humanly imaginable. Though 2^^^3 is only 2^16 or 25536 in decimal base, the pentation 3^^^3 raises a tower of powers 3^..3 of size :7625597484986 past a paper moon. Superpowers live in the so called Grzegorczyk hierarchy, to each *{c} its own class of numbers. But we would place 2*{c1}b\*{c}a halfway a*{c+1/2} between a*{c}b1 and a*{c1}b1 to create superrational arithmetic. $ 1.2. Og plane Extend the 'Og' system to multiple dimensions. -Og.4a ,[]1 ≡ 1 -Og.4b ,[1]1 ≡ ,1 -Og.5a a,b` 1?,[1m]1p `= a,` ,[m]ab,[1m]p Define Conway's chained arrows, with single recursion by y and double recursion by z over the chain X left. -Co.1 a→b = a^b -Co.2 X→1 = X -Co.3 X→1→z = X -Co.4 X→y1→z1 = X→(X→y→z1)→z == X→(..X..)→z :y: So that a→b→c equals a^{b}c superpowers. Approximate the 'Og' plane array with Conway's chained arrows. a,b,[2]c1 = a*{i}..b c:0 ~ 3→3→c a,0,[3]k ~ a→..a :k Proof follows. First let counter c expand the previous array row. a,,[2]c4 = a,,a,[2]c3 = a,,1,a*a,[2]c2 = a,,1,1,a^(a*a),[2]c1 = a,,1,1,1,a^^(a^(a*a)),[2]c == a*{i}..a c3:1 = a→(..a→2..)→i 1:c2 ~ 3→2→c4 = 3→(3→3→c2)→c2 = 3→(..3→3..)→i 1:c2 Here value a=5 fits best, but normal size a are insignificant. Recursion of the superstar counter creates Graham's numbers. a,,[2]c,2 ~ a,.,1..,[2]3→2→c :c ~ a,,[2]3→2→c :c ~ 3→2→(3→2→c) = 3*{3*{c}3}3 a,,[2]1,c1 = a,,[2]a,c ~ 3→2→(..a..) :c: = 3*{..a..}3 :c: ~ 3→2→c1→2 Each next parameter entry expresses a single recursion, over the whole second row a second double recursion, equal to Conway's chain of four. a,,[2]1,1,c2 = a,,[2]1,a,c1 ~ a,,[2]1,3→2→a→2,c ~ 3→2→(..a..)→2 :c1: ~ 3→2→c2→3 a,,[2].1,..c2 :d1 ~ a,,[2].1,..3→2→a→d1,c :d ~ 3→2→(..a..)→d1 :c1: ~ 3→2→c2→d2 Similarly a counter on the third row expands the length of the second. And each next entry recurses over the previous. In full a third double recursion, adding an arrow link to Conway's chain. a,,[2]1,[2]d3 = a,,[2]1,a,[2]d2 ~ a,,[2]1,1,3→2→2→3,[2]d1 ~ a,,[2]1,1,1,3→2→3→4,[2]d ~ a,,[2].1,..3→2→3→d3 :d2 ~ 3→2→3→d4 a,,[2]1,[2]1,d1 = a,,[2]a,d ~ 3→3→3→(..a..) :d: ~ 3→3→3→d→2 a,,[2]1,[2].1,..d2 :e1 ~ a,,[2]1,[2].1,..3→3→3→a→e1,d :e ~ 3→3→3→(..a..)→e1 :d1: ~ 3→3→3→d1→e2 The k rows in the 'Og' array plane pile up k double recursions, which equals a row of k2 big entries ! in Conway's chained arrows, a triple recursion. a,,[3]k3 = a,,[2]a,[3]k2 ~ a,,[2]1,[2]3→2→a,[3]k1 ~ a,,[2]1,[2]1,[2]3→3→3→2→2,[3]k ~ a,.,[2]1..,[2].3→..2→2 :k1 :k2 ~ 3→..2→2 :k3 ~ a!→..1 :k4 Separator ,[3] functions in the third dimension of 'Og', to expand a series of plane spaces. Recursion over its counter will beat Conway's chained arrows. $ 1.3. Dimensional arrays Our 'Og' system only has rules to add (copy) and shift (upload) numbers. Here we compare the power of 'Og''s multidimensional structure with that of Conway-Knuth superarrows, that substitute subexpressions on the right (without upload). Define the quadruple recursive →↑{k} Conway-Knuth superchained arrows, represented with a generic # arrow operator, but maybe ? missing. -Ck.1 X#1 = X -Ck.2 y#?↑z1 =` y#y#↑z == .y#..y :z -Ck.3 a#?→b = a#↑b -Ck.4 X#1→z = X -Ck.5 X#y1→z1 = X#(X#y→z1)→z == X#(..X..)→z :y: Note that a→b1 = a↑b1 = aa↑b is the left bitshift operation a*2^b instead of a power a^b1 at the start. From here on both are about equal. Single recursion over 'Og''s plane series, or over Conway's chain length. a,,[3]1,2 = a,,[3]a ~> a→↑a1 = a→..a :a a,,[3]1,3 ~ a,,[3]a→↑a1 ~> a→↑(a→↑a1) ~ a→↑3→2 a,,[3]1,b ~> a→↑b→2 Make that a double recursion, with an 'Og' array row in the second cube. a,,[3]1,1,2 ~> a→↑2→3 a,,[3]1,1,3 ~> a→↑3→3 a,,[3]1,1,b ~> a→↑b→3 a,,[3]1,1,1,b ~> a→↑b→4 a,,[3].1,..b :c ~> a→↑b→c1 Let the second 'Og' cube pile the next arrow row on top of Conway's, each plane a double recursion. a,,[3]1,[2]1,2 = a,,[3]1,[2]a ~> a,,[3].1,..a→↑a→a- :a- <~ a→↑a→2→2 a,,[3]1,[2]1,b <~ a→↑a→b→2 a,,[3]1,[2]1,1,b1 ~> a→↑a→b→3 a,,[3]1,[2]1,[2]1,2 ~ a,,[3]1,[2].1,..a! :a- <~ a→↑a→a→2→2 a,,[3]1.,[2]1..,b1 :c ~> a→↑.a→..b→2 :c ~> a→↑b→↑c1 a,,[3]1,[3]b,c1 ~ a,,[3]1,[3]a→↑a→↑b,c ~> a→↑a→↑b→2 So a sequence of separators ,[3] between planes in an 'Og' cube compares as equal to the arrow powers →↑ stacking a plane of Conway chains. a,,[4]b2 = a,,[3]a,[4]b1 ~ a,,[3]1,[3]a→↑a1,[4]b ~ a,.,[3]1..,[3]a→↑..a! :b :b ~ a→↑..(a!→↑↑b1) :b1 ~> a→↑↑b2 'Og' dimensions started with rows between ,[2] adding parameters →z to chained arrows. Now it appears 'Og''s array space lags consistently one dimension behind Conway-Knuth superarrows. a,,[c2]b ~> a→↑{c}b Here ↑{c} is a double recursive operator over a triple recursive chain →p_i.. in which each parameter →p piles up a double recursion. We call this quadruple recursive. Now does this compare to Bird's linear array function? $ 1.4. Birdy's linear array Develop the Birdy system B(X) with maximal substitution, and define upload rules that are stepwise (where Bird fills array spaces). Only clean up at bracket ends, so evaluation remains simple and thrifty. Birdy should always be about as powerful as Bird's arrays for expressing big numbers. Here we will also prove that Birdy's first row approximates Conway-Knuth superchained arrows or multidimensional 'Og'. We write Birdy function expression B(X) as its content X or (X) inside. Parameter values in rules are not 0 zero. By == rules are repeated. -B.1. (a) = a -B.2. (X,1) = (X) -B.3. (a,b1) = (a,b)a == (a,1).a.. :b = a.. :b1 = a*b1 -B.4. (a,1,X) = a -B.5. (a,b1,2X) = a,(a,b,2X),1X == (a,..a..,1X) :b: -B.6a. (a,b.,1..1X) :k1>1 = a,a.,1..b,1X :k == a,a,1.a,..b,X :k- Birdy a,b starts with multiplication a*b and subexpression substitution in motor rule '5.' is the same as Bird who starts with a**b powers. So if we add 1 to our superstar counter it is equal to that of Bird. We try to keep a difference of 1 between us, and design any Birdy row with the double recursion c1 to be exactly Bird's linear array with third entry c . From a Birdy array a,b1,X in rule '5.' the subexpression $ is a,b,X minimally decremented on the left, and to be substituted maximally. This function substitution starts double recursive, which is similar to Conway's chained arrows. But Bird and Birdy reload high iterators ,1 waiting on the right, while Conway drops iterators from the chain once counted off. And so the Birds express significantly bigger numbers. Past superpowers, Conway uses his whole third entry in a→b→c→2 to express a recursion that yields Graham's numbers, while Birds count off the second entry: Bird in {a,b,1,2} uploading $ by rule, and Birdy with a,b,2,2 stepwise, reducing the substitute $ to subtotal b before upload. {a,b1,1,2} = {a,a,{a,b,1,2}} == {a,a,..a..} :b: a,b3,2,2 = a,(a,b2,2,2),1,2 == a,(..a..),1,2 :b2: = a,(..a,a,a1..),1,2 :b1: := a,(..a,a,(a,a,a1)1..),1,2 :b: == (a,a,..a..1) :b2: Each c inside Birdy adds 1 to that in Bird, expressing the same superpower. The four entry arrays can be adjusted exactly. The rule for function substitution is the same, so we only need to align cases of upload. {a,b1,1,d1} = {a,a,{a,b,1,d1},d} == {a,a,..a..,d} :b: a,b2,2,d1 = a,(a,b1,2,d1),1,d1 == a,(..a..),1,d1 :b1: = a,(..a,a,a1,d..),1,d1 :b: :== (a,a,..a..1,d) :b1: Make upload in five entry arrays work out to equal expressions. {a,b1,1,1,2} = {a,a,a,{a,b,1,1,2}} == {a,a,a,..a..} :b: a,b2,2,1,2 = a,(a,b1,2,1,2),1,1,2 == a,(..a..),1,1,2 :b1: = a,(..a,a,a1,a..),1,1,2 :b: :== (a,a,a1,..a..) :b1: Generally for upload on the row, with b>1 and some k entries 1 waiting to the right, Birds can express equal numbers. {a,b.,1..X} :k = {.a,..$,X} :k a,b,2.,1..X :k1 = a,$.,1..X :k2 := a,a,1.a,..$,X :k So Birdy maintains an exact difference of c1 against Bird c during evaluation. By comparing Birdy with superchained arrows we can compare Bird with 'Og'. $ 1.5. Fourfold recursions Now compare various expressions of double recursion in big number systems. Conway-Knuth arrows 'Ck' were defined to start with a↑b repeated doubling or a left bitshift. Recursively this is about ~ the same as a^b powers. a↑b1 = aa↑b == a*2^b := B(a,(1+log(2)/log(a)*b),2) a→b1→2 = a↑(a→b→2) == a↑..a :b = a*2^(..a..) :b := B(a,..a¡..,2) :b <≈ B(a,b1,3) a→b1→c1 == a→(..a..)→c :b := a↑{c}b <≈ a*{c1}b = B(a,b,c1) = Bird{a,b,c} = Og(a,.,1..,b) :c <~ a,b,[2]c2 That a¡>2 is a smaller number than a is insignificant, check 100¡≈16 here. Compare Graham's numbers again, the single recursion after double recursion. a→a→b1→2 = a→a→(a→a→b→2) == a→a→(..a↑a..) :b: ≈> 2^{..1..}a :b1 ~> B(a,b1,2,2) = (a,(a,b,2,2),1,2) := (a,a,1(a,b,2,2)) == (a,a,1..a..) :b: <~ Og(a,1,[2]1,b1) = a,,a,[2]a1,b = a,,1,a*a,[2]a,b ~ a,a^{a}a.,1..,[2]1,b :a1 ~ a^{..a..}a :b: This nests quite naturally in parameter c under d=2 in Conway's chain, and uploads from b under c=2,d=2 in the four entry array of Birds. In system 'Og' single recursions are piled up on the first row, so the ,[2]c on the second row counts superpowers. Row and row counter are double recursive. Under next entry ,[2]1,d the subtotal sum will be uploaded repeatedly to the row counter, which puts one single recursion on top. Under any next parameter n in 'Og' we have single recursion over its left expression part L by repeated upload of subtotal sums in position m . Og(L,m,n1,R) = L,(L,m),n,R ~ L,(L,(L,m)),n-,R ~ L,(..L,m..).,1,R :n: The evaluation is not exact ~ because the sizes of rows and other spaces inside L increase during evaluation. But every higher iteration the uploaded sum values dominate all its lower spaces, so simple subexpression nesting forms a good approximation. Also for the recursion under :n and those right after, it is not so significant if L,m is fully counted down. Else, if it is part of an input expression and has to be evaluated, we could add about 1 to the iterator n instead. Next in the construction a recursion in place of n is uploaded, and so on. By appending single recursive parameters in 'Og' we get the double recursion of the second row. This is comparable to arrow →d in Conway's chain of four, and to entry c1 under d=2 in Birdy for Bird. a→a→b1→c1 = a→a→(..a↑a..)→c :b: ~> B(a,b1,c1,2) = (a,(a,b,c1,2),c,2) == (a,..a..,c,2) :b: <~ Og(a,b,[2]1,[2]c1) Every row in 'Og' adds a series of single recursions that form a double recursion under ,[2] in a plane array. This plane of 'Og' should equal Conway's chained arrows, as covered by the full entry d in Birdy. This we call triple recursion. Time to open the third dimension ,[3] in 'Og' with a plane counter appending a number of row spaces of growing length. Much like Conway-Knuth arrow →↑ expanding the chain of Conway, or Birds uploading the fourth entry. a→↑b2 = a→a→↑b1 == a→..a :b1 <≈ B(a,b,1,1,2) = (a,a,a1,b) <~ Og(a,,[3]b1) = a,,[2]a,[3]b ~ a,.,[2]1..a! :b Clearly in Birdy double recursion is expressed again in entry c and the next Conway chain in entry d so that entry e must compare to a series of →↑ superations of length e . Further entry f a series of →↑↑ etc. Generally Birdy or Bird's linear array with size k4 compares to a series of →↑{k} Conway-Knuth superarrows. Completing those systems with what we call a quadruple recursion. In turn the ,[k2] dimension in 'Og' stacks like →↑{k} superarrows. Both are multidimensional spaces and cover the same big numbers as Bird's linear array. The difference is just one separator index. $ 2. Beyond nested arrays See how 'Og' and Birdy become equally powerful systems for the creation of big numbers, as we define advanced rules for nesting arrays and beyond. $ 2.1. Nested arrays Define nested array rows in 'Og' by extending rule '5a' for dimensional separator ,[m] indices to nested sep ,[S] index arrays. Where the text variables are closed [] for array brackets, so that any bracket in subarray S or empty left part L or right part R forms a pair inside. -Og.5b a,b` 1?,[1S]1p `= a,` ,[S]ab,[1S]p -Og.6 ,]1 ≡ ]1 -Og.7 a,` ,[L,1R]b `= a,` ,[Lb,R]a -Og.8 a,` ,[L,[1S]1R]b `= a,` ,[L,[S]b,[1S]R]a Left part L = ,[L_i].. :k≥0 has no iterations left, but the right part R of the selected array may well have. Important is that rules '7' and '8' descend the big number b inside the subarray, after part L just emptied its iterations. Sum b was previously uploaded by rule '5b' in the insert ,[S]ab when the first index of S now in part L apparently became empty. Rule '7' has precedence over rule '3' and rule '8' over rule '5', because that left scan rule `= is evaluated where selections start earlier in the expression. So that rule '3' and '5' apply to parameters on the top level of the expression, and rule '7' and '8' are to reload index subarrays. The Birdy nested system is adapted in a similar fashion. -B.6b a,b,` ,1p `= a,a,` b,p -B.7 ,[] ≡ 0 & ,[1] ≡ , -B.8 a,b` ,[1S]1p `= a,a` ,[S]b,[1S]p Birds' multidimensional arrays ,[n] can be categorized as fivefold recursion, which compares to 'Og' with ,[m,n] sep arrays. With the first nested row of sep indices expressions of 'Og' and Birdy run on a par, and are called hyperdimensional arrays. These double level array rows can be seen as sixfold recursion. Followed by the arbitrary level nested arrays defined here as sevenfold recursion. The difference between Birdy and 'Og' is just one hyperdimensional sep index in each nested row. When array expressions have a second level index both systems will appear the same; their algorithms equalized by the structure. Nested subexpressions are worked out to a number b in place, before uploading this subtotal as an iterator. But when separator arrays are nested, that is usually not in one place, but spread out over the whole expression. It is informationally consistent that Bird's maximal rule of nesting subexpressions soon loses its advantage there. $ 2.2. Deeps We have a construction now where the index rows in each separator array can be nested to arbitrary depth. This subarray functions as a complete whole, like the unit one 1 , but in a higher cycle or reincarnation. Analogous to unary numbers 1.. we can expand our subarray unit to a series ,.[S_i].. of nested subarrays. Recursion zero starts with numbers, in which units are equal, added without order. But here each right subarray will nest the subarray it is appended to to greater depth. Therefore we call these reincarnated number constructs "deeps". And their hierarchical depth expansion counts as eightfold recursion. -Og.9 ][]1 ≡ ]1 -Og.10 a` ,[L][1S]b `= a` ,[,[L][S]b]a So that a,,[][t1]p = a,,[,[][t]p]a == a,.,[..,[][]p..]a :t1: = a,.,[..p..]a :t1: a,,[][t,1T]p! == a,.,[..,[][a,T]p!..]a :t: . . . . . Ninefold recursion as the next number cycle is completed.