Bowers Exploding Array Function discussion part 1: Linear and planar arrays
Well, it's been another full year without me making a post about people's attempts at formally defining Jonathan Bowers' Exploding Array Notation. This post is the first in an attempted series to discuss the rules for some subsystems of BEAF and the various ways that people have interpreted Bowers’ unformalized ideas of “array spaces.”
I begin by introducing arrays in a somewhat non-traditional way, which is similar to the description from Bowers' Spaces page (Some people have trouble loading the page so the Internet Archive link should also work: http://web.archive.org/web/20201102164403/http://www.polytope.net/hedrondude/spaces.htm). My goal is to emphasize the structure of the space the array lives in, rather than the array itself. I won't spend much time going over example calculations to give a sense of how unimaginably large the numbers get, either. There is a good explanation on Googology Wiki of how BEAF easily creates numbers that surpass Graham's number, as well as the most common large number generating functions, such as up-arrow notation and chained arrow notation: https://googology.wikia.org/wiki/Introduction_to_BEAF.
Linear arrays
To understand linear arrays, just imagine an infinite row of boxes where positive integers can be placed. The row has a beginning but no end. Each box is indexed by an integer, and for the purpose of this discussion we will say these indices start at 0. The default value for a box is 1, and all but finitely many boxes must contain the value 1. When we write an array like this: {a, b, c...}, the values in the brackets are in sequential positions starting from entry 0, and all remaining entries are 1, so the array is inside an infinite sea of 1's. In general, an array can be considered a collection of numbers at various positions inside an infinite (hyper-)dimensional space of 1's.
Bowers has a lot of terms for various entries in the array which he uses when he defines his rules. Definitions:
Entry 0 is called the base.
Entry 1 is called the prime.
The first entry after the prime that is not 1 is called the pilot.
The entry right before the pilot is called the copilot.
The array is solved into an integer by means of applying a series of steps repeatedly until either the base rule or prime rule applies, and then a value is returned.
Rules
Let b be the base and p be the prime.
Base rule: If every entry besides the base and the prime is 1, the array evaluates to b^p.
Prime rule: If p = 1, the value b is returned.
Catastrophic rule: If neither of the above rules apply, the array is changed in the following way:
The pilot is decreased by 1.
The copilot becomes the value of the original array, but with the prime decreased by 1.
Besides the copilot, every entry before the pilot changes to b.
Planar arrays
The next step is to stack the numbers on top of each other. The array can be imagined as an infinite plane of boxes of positive integers. This time, the positions in the array can be described by two coordinates: (a, b) is the value in the a-th row and b-th column (and a and b both start from 0). 1's are still the default value, so for a valid array, all but finitely many entries are 1's.
Bowers still uses commas to separate the entries of the array, and uses the separator (1) to move to the first entry on the next row. Thus, an array such as {3, 3, 3 (1) 3, 4, 5, 6} means the following structure in space: 3 3 3 1 1 1... 3 4 5 6 1 1... 1 1 1 1 1 1...
...
Most of the rules and definitions we gave above still work. The base and prime are now the entries at positions (0, 0) and (0, 1) respectively (i.e., on the first row). The pilot may not be on the first row anymore; it may be on the second row, third row, or beyond. If the pilot is the first entry on its row, the copilot doesn't even exist.
There are two important things to understand about the definition of the pilot: "The first entry after the prime entry that is not 1." First, it requires that all the positions of space have an ordering. The ordering is just the standard top-to-bottom left-to-right reading order: (w, x) > (y, z) if w > y, or if w = y and x > z. Second, the entries must be well-ordered; that is, each non-empty set of space positions must contain one that comes first in the ordering. If the entries were not well-ordered (for example, if the second coordinate were always non-positive instead of non-negative), we would not be able to ensure that the set of entries after a certain position contains an earliest entry (for example, the position (1, 0)), and thus we could not speak of the first non-1 entry after the prime. This well-ordering requirement must apply to all extensions of BEAF and it will force the different levels of array space into a hierarchy that is unavoidable, up to isomorphism.
The only rule that needs to change is the catastrophic rule. First, we need a minor tweak to the second part of the rule in case the copilot doesn't exist:
The copilot (if it exists) becomes the value of the original array, but with the prime decreased by 1.
The third part of the rule no longer works either:
Besides the copilot, every entry before the pilot changes to b.
This is because, if the pilot is on the second row or beyond, an infinite number of entries on the first row must become b. This violates the requirement that only a finite number of entries can be non-1. Instead, Bowers decides that for all rows above the pilot, the first p entries change to b. The rest of the rows' entries (which are all 1's anyway) stay the same.
This means that if the pilot is at (y, z), a chunk of y*p + z prior entries take on the value b. Bowers calls the p entries on each row the prime block of the row. However, we can speak of the prime block of any position in array space as all of the entries that would be filled if the pilot or copilot was at that space (Bowers also calls these entries the "airplane"). Because the size of the prime block is a linear polynomial of p, the positions themselves are often expressed as polynomials, with position (y, z) described as y*X + z. The prime block itself can be represented by [y*X + z](p).
In fact, if the pilot is 2, and every other entry besides the base and prime is 1, the array evaluates into just a prime block and nothing else (besides trailing 1′s). This is how Bowers constructs many of his larger named numbers, which are usually written as {b, p (separator) 2} or as f(p) & b (where f is a function identifying a space by the size of its prime block, and & means "array of").