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.
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 takes on the value of 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. 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) 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.
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 2+2X+1)\uparrow\uparrow X\) 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).
The Googology Wiki users Deedlit11^{[2]} and Ikosarakt1^{[3]} have defined the pentational arrays–each in a separate way–and came to the same results, which agree with Bowers' beginning of this work.
Larger non-legion arrays
There are larger arrays like hexational, heptational, 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.)
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^{[4]} (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, \(3^2 \& 3 = \{ 3, 3, 3 (1) 3, 3, 3 (1) 3, 3, 3 \}\) is a 3 by 3 \( = 3^2\) array of 3's.
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\} = 3 \& 3 \& 3 = \{3, 3, 3\} \& 3\) (a pentational array with tritri entries known as triakulus).
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 (\1,2) 7,8 (\3) 2} (a dimensional lugion array), {5,5,5 \\\\\\ 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, and 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 intended to be a computable function, BEAF is naturally beaten by \(\Sigma(n)\), \(\Xi(n)\), Rayo's function etc. However, since BEAF is unformalised, even its computabilty does not mathematically make sense.
Sources
- ↑ Array Notation
- ↑ User blog:Deedlit11/A rigorous definition for pentational arrays
- ↑ User blog:Ikosarakt1/Introduction to pentational arrays
- ↑ User blog:Deedlit11/Rigorous definition for hexational arrays and beyond
See also
- Introduction to BEAF
- Bird's Array Notation
- Array Notation
- Extended Array Notation
- Array of
- G function
- Jonathan Bowers
External link: Personal website