Bowers' Exploding Array Function (BEAF) is a notation for very large numbers invented by Jonathan Bowers, similar to chained arrow notation, but far stronger. It is a superset of array notation and extended array notation, both invented by Bowers.[1] It has become quite famous in googology due to its simplicity and growth speed, not to mention the vast array of whimsically named numbers defined with the function (such as golapulus and the legendary meameamealokkapoowa oompa, one of Bowers' largest numbers). However, there is no agreed-upon definition for the notation above tetrational arrays. Therefore, strictly speaking, BEAF beyond tetrational arrays is ill-defined, although BEAF before tetrational arrays is well-defined.
Although Chris Bird and John Spencer (a friend of Bowers') assisted in the construction of BEAF, Bowers is usually given sole credit for the function.
Sbiis Saibian mentioned that the existence of a notation which fully satisfies Bowers' rules is an open problem in googology. Although he only directly mentions pentational arrays, it probably refers to other levels of BEAF as well.[2]
Definitions[]
Here is a rough sketch of how it is roughly intended to work. As we explained above, there is no agreed-upon definition of the original BEAF beyond tetrational arrays, and hence it is not a complete definition.
- The "base" (b) is the first entry in the array.
- The "prime" (p) is the second entry in the array.
- The "pilot" is the first non-1 entry after the prime. It can be as early as the third entry.
- The "copilot" is the entry immediately before the pilot. The copilot does not exist if the pilot is the first entry in its row.
- A "structure" is a part of the array that consists of a lower-dimensional group. This could be an entry (written \(X^0\)), a row (written \(X^1\)), a plane (\(X^2\)), a realm (\(X^3\)), or a flune (\(X^4\)), not to mention higher-dimensional structures (\(X^5\), \(X^6\), etc.) and tetrational structures, e.g. \(X\uparrow\uparrow 3\). We can also continue with pentational, hexational, ..., expandal, ... structures.
- A "previous entry" is an entry that occurs before the pilot, but is on the same row as all other previous entries. A "previous row" is a row that occurs before the pilot's row, but is on the same plane as all other previous rows. A "previous plane" is a plane that occurs before the pilot's plane, but is on the same realm as all other previous planes, etc. These are called "previous structures."
- A "prime block" of a structure \(S\) is computed by replacing all instances of \(X\) with \(p\). For example, if \(S = X^3\), the prime block is \(p^3\), or a cube of side length \(p\). The prime block of an \(X^X\) structure is \(p^p\), a \(p\)-hypercube with side length \(p\).
- The "airplane" includes the pilot, all previous entries, and the prime block of all previous structures.
- The "passengers" are the entries in the airplane that are not the pilot or copilot.
- The value of the array is notated \(v(A)\), where A is the array.
Rules[]
- Prime rule: If \(p = 1\), \(v(A) = b\).
- Initial rule: If there is no pilot, \(v(A) = b^p\).
- Catastrophic rule: If neither 1 nor 2 apply, then:
- pilot decreases by 1,
- copilot becomes the original array with the prime decreased by 1,
- each passenger becomes b,
- and the rest of the array remains unchanged.
Array types[]
Linear arrays[]
- Main article: Array notation
Linear arrays are the smallest and simplest type of array. A linear array consists of a one-dimensional row of numbers, e.g. \(\{5,8,7,2,4\}\). Although they are the smallest of BEAF arrays, linear arrays with more than four entries grow much, much faster than chained arrow notation (a theorem known as Bird's Proof). Positions in linear arrays can be described with a single number, e.g. the fourth entry.
Dimensional arrays[]
- Main article: Extended Array Notation
Dimensional arrays are arrays that need 2 or more dimensions to represent. [1]To write these arrays in a single line, one must use numbers in parentheses in place of commas to indicate breaks in multiple dimensions. (1), a fixed-point of {X} = {X, 1, 1, 1, 1, 1, 1...1, 1, 1, 1, 2}, means that the following numbers are in the next row, (2) means the next plane, (3) means the next realm (3-space), (4) means the next flune (4-space), and so forth. For example, \(\{3,3,3 (1) 3,3,3 (1) 3,3,3\}\) means a 3-by-3 square of threes. Positions in dimensional arrays require linear arrays to represent. For example, \((5,6,8,2)\) means the fifth entry on the sixth row on the eighth plane in the second realm. These structures also can be called exponential arrays.
Tetrational arrays[]
Tetrational arrays are arrays that require tetrational spaces to represent. They are the largest part of BEAF with an agreed-upon definition in the googology community, and therefore they are arguably the largest well-defined part of BEAF. Tetrational spaces consist of superdimensional space, trimensional space, quadramensional space, etc.
Superdimensional arrays consist of not only dimensional spaces, but also dimensional groups, dimensional spaces of groups, groups of groups, gangs (the next structure level after the group), etc.
Positions in superdimensional arrays require dimensional arrays to represent, positions in trimensional arrays require superdimensional arrays to represent, etc.
To represent a tetrational array, you will need to use (0, x) if you want to represent superdimensional arrays, in (a, b, c, d...), a represents the dimensions, b represents the superdimensions, c represents the trimensions, d represents quadramensions, and so on to finish dimensional groups. We are roughly at an X tetrated to 3 array of 10's once we reach the limit of dimensional groups. We can go further by nesting a (1) fixed-point within (X) to form our dimensions in groups, and our groups of groups. To understand how tetrational arrays work, we would start with an array of size X^^4, or X^X^X^X & 10. This is equal to around {10, 100((0, 1)1)2}, or a goduplexulus. We can increase our array into an X^X^X^X+1-sized array, then a 2X^X^X^X-sized array, until the *2 becomes a *X, where, under the laws of exponents, sends a +1 to the second level of the power tower (as a*ab=ab+1), and (aa^a)a=aa*a^a=aa^(a+1). Once We can continue to multiply our array by X to make the +1 into a +2, until it becomes a *2, and a *X, so our +1 then reaches the third level. Eventually, the +1 will reach the top of the power tower. We can extend our power tower by adding a 1 on the next level without changing its value, so a +1 to the 1 on top tops the power tower with a 2. We can continue ascending +1's and *2's to top the power tower with a 3, then a 4, and finally an X, and then our power tower gets raised by one level into an X^^5-sized array of 10's, {10, 100(((1)1)1)2}, or a gotriplexulus. We can keep building our power tower by nesting more (1) fixed-points until we reach the limit of tetrational spaces, or X^^X & 10.
Pentational arrays[]
On pentational arrays, the powers sort into groups, like \(X \uparrow \{X\uparrow X\uparrow X\} \uparrow \{X\uparrow X\uparrow X\} \uparrow \{\{X\uparrow X\uparrow X\} \uparrow \{X\uparrow X\uparrow X\} \uparrow \{X\uparrow X\uparrow X\}\}\) or \(X \uparrow\uparrow (X \uparrow 2+2X+1)\) where X is evaluated at 3. The {} are not to be solved like ordinary parentheses, but are used to group up the exponents into tetrational blocks (so if the prime entry changes, then the number of X's or {X^...^X} on each block will also be changed to the prime entry). Pentational arrays are like tetrational arrays, but with a variable number of terms in the power tower instead of a discrete number of terms, which includes X^^X, X^^(X+1), X^^2X, X^^X2, X^^XX, X^^X^^X, and the limit of that is X^^^X.
The Googology Wiki users Deedlit11[3] and Ikosarakt1[4] have defined the pentational arrays via non-climbing method–each in a separate way–and came to the same results, which agree with Bowers' beginning of this work, but both have a discrepancy with the rule "A&n has A(n) entries" and so can not be considered as valid attempts.
Larger non-legion arrays[]
There are larger arrays like hexational, heptational, trientrical, expandal, multiexpandal, powerexpandal, explodal, multiexplodal, detonational, etc. Eventually, we create a really large array that the space its in needs to be represented by array notation (linear, dimensional, tetrational, etc.), also known as "nested" arrays, or "array of" array spaces.
Jonathan Bowers comments on these arrays, "How to work with these? - Only God knows - but they should form some massive arrays - and utterly unspeakable numbers when solved."
Deedlit11 also has defined "arrowal" arrays[5] (hexational, heptational and others that are defined in terms of Knuth's arrays) and they presumably confirm Bowers' results–but a confirmation of these results don't exist yet.
Legions[]
Before discussing legions, we must first define the array of operator. a array of b, written a & b, is defined as {b, b, b, ...}, in which there are a b's. If a is an exponent or array, it indicates the dimensions of the resulting array. For example, \(X^2 \& 3 = \{ 3, 3, 3 (1) 3, 3, 3 (1) 3, 3, 3 \}\) is a 3 by 3 \( = X^2\) array of 3's. In any BEAF array, cardinality matters, as in an array of size 10 + 1 & 10, cardinality doesn't matter, which produces a degenerate linear array of 11 10's, equivalent to {10, 10+1(1)2}. If cardinality matters, then the array will have size X + 1 & 10, (with the X's grouped), and then, that is equal to {10, 10(1)10}.
Bowers further extends BEAF using legion arrays (in his old notation, he used the term "exploded arrays"). In the array \(\{ a, b, c, \cdots / 2\}\), we say that the number 2 is in the second legion. In such a case, we solve the array in the first legion normally, but in the initial rule, we say that \(v(A) = b \& b \& b \& b \& \cdots b \& b \& b \& b \) p times, solving from left to right. For example, \(\{ 3, 3 / 2\} = X \& X \& 3 = \{3, 3, 3\} \& 3\) (a pentational array with tritri entries known as triakulus). Since Bowers didn't make it to nested arrays, the nested arrays are still "under construction", and BEAF is still in its beta versions. Therefore, an array of size X+1 & X & 10 is equal to {10, X+1(1)2} & 10, an X+1-sized linear array of X's in an array of 10's. This clearly slows down BEAF in a way, so the legion arrays start at the large Veblen ordinal, or {10, X, 2(1)2} & 10. This causes large arrays like this to become ill-defined. One possible way to solve this is to create an X2 to represent {10, X(1)X}, a grouped array within an array, with the X2 exponent to indicate the dimensions of the nesting array rather than an Xn-sized linear array of X's nested in an array of 10's causing legion arrays to occur at a higher ordinal.
In the general case \(\{b, p / x\}\), \(x\) is the pilot. The prime block of a legion is \(b \& b \& ... \& b \& b\) \(p\) times, giving us the general case:
\[\{ b, p / x + 1\} = \{ b \& b \& b \cdots b \& b \& b / x\}\]
For example:
\[\{ 3,3 / 3\} = \{ 3 \& 3 \& 3 / 2\}\]
Now the first legion contains a \(3 \uparrow\uparrow\uparrow 3\) array of threes, which must then be solved in the second level of legion arrays.
We can also have multiple arrays in the second legion, such as \(\{3, 3 / 3, 3\}\). Each legion can be dimensional, tetrational, pentational, expansional, etc. An array can also have more than two legions, e.g. \(\{ 3, 4 / 5, 6 / 7, 8\}\). The structure of the legions can be multidimensional, using (/n) to indicate an n-dimensional legion break, e.g. \(\{ 3, 4 (/6, 2) 9, 4\}\) is a tetrational legion array.
Ones are still default in legion arrays: \(\{ A / 1\} = \{A\}\).
Multiple legions, legiattic arrays[]
To continue this further, need to explain "legion array of" symbol: &&. It works as standard "array of" symbol, but on legion arrays, e.g. 3 && 3 = {3,3 (/1) 2} = {3 & 3 & 3 / 3 & 3 & 3 / 3 & 3 & 3} (here / works as commas in standard arrays), and Bowers defines the double legion mark (e.g. {3,3 // 2}) as repeated legion "array of" symbol: \(\lbrace a,b // 2\rbrace = a\&\&a\&\&a\cdots a\&\&a\&\&a\) (b times)
Double legion arrays, of course, might be multidimensional, tetrational and beyond, up to double legions itself. It makes sense to define triple legion arrays as repeated double legion marks, quadruple as repeated triple legion marks, and so on.
Beyond this, need to define the new structure: \(\{ a,b (1)/ 2\} = \{ a,b ///.../// 2 \}\) (b \(/\)'s) (legion mark in the next row of legion marks takes under prime block a previous row of legion marks). Legion marks might be array itself, constructs structures like \(\{ a,b ///(2)/(3)//(4)/(1,2)/ 2 \}\).
To extend this even further, Bowers defines new notation: \(\{ L,1\}_{a,b} = \{ a,b / 2\}, \{ L,2\}_{a,b} = \{ a,b // 2\}, \{ L,X\}_{a,b} = \{ a,b (1)/ 2\}\). This is only small examples of legiattic arrays, or "legion marks" arrays, there exists \(\{ L,X \uparrow\uparrow\uparrow X \}_{a,b}\), a pentational legiattic array. There are also arrays like \(\{ L,L \}_{a,b}\), legion legiattic array, legion marks on legion marks. There are things like
\(\{L,3,2\}_{a,b}\), \(\{L,L,L\}_{a,b}\), \(\{L,L (1) 2\}_{a,b}\). It is appropriate to define a legiattic "array of" mark: \(a @ b = \{L,L,L,...,L,L,L\}_{a,b}\) (b L's) \(a^{2} @ b = \{L,L,L,...,L,L,L(1)L,L,L,...,L,L,L(1)...(1)L,L,L,...,L,L,L(1)L,L,L,...,L,L,L\}_{a,b}\) For example, \(3^{3} @ 3 = \{L,L,L(1)L,L,L(1)L,L,L(2)L,L,L(1)L,L,L(1)L,L,L(2)L,L,L(1)L,L,L(1)L,L,L\}_{a,b}\).
Lugions, lagions, ligions, and beyond[]
Firstly, Bowers defines {a,b \ 2} = a @ a @ a ... a @ a @ a (b a's), where \ is a lugion mark. No problem to extend it further, we can create \(\{3,4,5 (\backslash 1,2) 7,8 (\backslash 3) 2\}\) (a dimensional lugion array), \(\{5,5,5 \backslash\backslash\backslash\backslash\backslash\backslash 3\}\) (a sextuple lugion array). Lugion space is L2 space, and so {L2,X}a,b = {a,b (1)\ 2}. From this it is easy to go to lugiattic arrays, or "lugion marks" arrays. Lugiattic "array of" mark is %, and repeated lugiattic "array of" marks called lagions: {a,b | 2} = a % a % a ... a % a % a (b a's). Repeated lagiattic "array of" marks called ligions: {a,b - 2} = a # a # a ... a # a # a (b a's).
Then notice how legion space is L1, lugion space is L2, lagion space is L3, ligion space is L4, we can continue to L5, L6,... spaces, and structures like LX, L(X+1), L(X+2), L(2X), L(X^^^X), LL, LLL.
L's can form an array itself, e.g. {LLL(1)LLL(2)LLL(1)LLL,10}3,3, and {(1)L,10}3,3 = {LLL,10}3,3. L arrays (not to be confused with legiattic arrays) can be dimensional, superdimensional, trimensional, tetrational, ... , legiattic, lugiattic, lagiattic, ligiattic, L100-attic, LL-attic, etc. L arrays can be large enough to be represented with lower L arrays, which are then represented with lower L arrays themselves... and that's the limit of BEAF.
Analysis[]
Even low-level BEAF easily passes the Ackermann function, Knuth's arrow notation (of which it is an extension), Conway's chained arrow notation, and Saibian's hyper-E notation. BEAF only has an agreed-upon definition up to tetrational arrays (which fall at the ordinal level of \(\varepsilon_0\) in the Fast-growing hierarchy). Googology Wiki user hyp cos has made an informal analysis on how powerful BEAF "should" be. It can be found here, here, and here. However, this analysis should not be taken too seriously, as it assigns growth rates to ill-defined portions of BEAF.
Since it is a computable function, tetrational-level BEAF is naturally beaten by \(\Sigma(n)\), \(\Xi(n)\), Rayo's function etc. However, since BEAF is unformalised beyond tetrational arrays and the existence of its formalization remains an important open problem in googology, its computability beyond tetrational arrays does not mathematically make sense.
Sources[]
See also[]
- Introduction to BEAF
- Bird's Array Notation
- Array Notation
- Extended Array Notation
- Array of
- G function
- Jonathan Bowers
External link: Personal website