Introduction to Bashicu matrix system

==Introduction==
The Bashicu Matrix System (BMS) is a large number notation devised by Googology Wiki user . The notation is commonly written as a sequence of \(k\)-tuples of nonnegative integers written next to each other with no spaces, such as (0,0,0)(1,1,1)(2,1,0)(1,1,1). Often, an extra element is added to the end, consisting of a single integer enclosed in square brackets, such as (0,0,0)(1,1,1)(2,1,0)(1,1,1)[5]. Each \(k\)-tuple corresponds to a column in the matrix.
There are many different versions of BMS created from 2014 onwards, and the version explained here is "Bashicu Matrix version 4" (BM4).
A subsystem of Bashicu Matrix System that consists of matrices with only one row (so the length of each tuple is 1) is known as the Primitive Sequence System, or PrSS for short. It has an ordinal limit of \(\varepsilon_0\).
A subsystem that consists of matrices with at most 2 rows is called the Pair Sequence System, or PSS. Googology wiki user P進大好きbot proved the termination of this subsystem, which has ordinal limit of \(\psi_0(\Omega_\omega)\) with respect to Buchholz's function.
A subsystem that consists of matrices with at most 3 rows is called the Trio Sequence System, or TSS. This subsystem suddenly becomes very strong if it actually terminates. Although its termination is unknown, it is believed to be more powerful than almost all other known ordinal notations, with only a few exceptions, such as Taranovsky's C.
There are also subsystems that consist of matrices with more than 4 rows (n-sequence BMS). Again, it is unknown if these systems actually terminate, but if they do, they are expected to be extremely powerful.
==Primitive Sequence System==
Primitive sequence system (PrSS) is the most basic form of BMS, having only 1 row. A matrix looks like this: (a)(b)(c)... where a, b, c... are all non-negative integers. A column is an area surrounded by two parentheses including only numbers or commas. Matrices may be followed by [n] where n is a non-negative integer. (If you are familiar with the fast-growing hierarchy, or other similar notations, [n] is exactly the fundamental sequence function except for cases where the matrix is followed by a column of 0s.) Here are some example matrices:
*(0)(1)(2)
*(0)(1)(2)(3)
*(0)(1)(1)
Expansion of a term \((a_1)(a_2)\dots(a_n)[m]\) proceeds as follows:
*If the last term equals (0), then remove it and square the number in the square brackets.
*Otherwise, find the rightmost term whose number is less than \(a_n\), we will call this term \((a_i)\). This term is known as the bad root. Denote \((a_1)(a_2)\dots(a_{i-1})\) by the "good part" G, and denote \((a_i)(a_{i+1})\dots(a_{n-1})\) by the "bad part" B. To evaluate \((a_1)(a_2)\dots(a_n)[m]\), we take G, followed by \(m\) copies of B. Finally, we take the square of the number in the square brackets (so it will become \(m^2\)).
Example:
*(0)(1)(2)(2)[3]
The number on the right end is 2, so we have to look for the bad root, which is rightmost number less than 2. This is the second term, the (1).
*(0)(1)(2)(2)
The good part therefore consists of everything to the left of the (1), which is just the (0). The bad part consists of the (1) and everything up to, but not including, the last term. The bad part is therefore (1)(2).
To expand (0)(1)(2)(2)[3], we take the good part, followed by 3 copies of the bad part, which is
*(0)(1)(2)(1)(2)(1)(2)
And then we take the square of 3, which becomes the new number in square brackets:
*(0)(1)(2)(1)(2)(1)(2)[9]
This is the desired result.
Note: It is possible for either the good part to be empty. If the bad root is the very first term in the sequence, the good part will have length 0. In this case, its expansion simply consists of the bad part repeated \(m\) times, where \(m\) is the number in square brackets.
Note: If we instead simply added 1 to the number in square brackets, instead of squaring it as Bashicu originally defined, the notation would not be any less powerful. In fact, we can simply leave out the number in square brackets entirely. Doing so would turn BMS from a large number notation to an ordinal notation.
==Pair Sequence System==
Pair Sequence System (PSS) is the same as BMS except with matrices restricted to two rows. This time a matrix looks like (a,b)(c,d)(e,f)... where a, b, c, d, e, f... are all non-negative integers. The nth row is an array of the nth entries of each column. Everything else, except when otherwise stated, is the same. The following are valid matrices in PSS:
*(0,0)(1,1)(2,0)(1,1)
*(0,0)(1,1)(2,2)
Finding the expansion of a PSS matrix is more complicated than PrSS. If the last element is (0,0), then just remove it and square the number in the brackets. Otherwise, if the last column is of the form (a,0) for some a > 0, then the process is nearly the same as PrSS. Find the rightmost element (b,c) such that b<a, and this element is the bad root. After this, the expansion process is identical to PrSS.
However, if the last column is of the form (a,b) for b>0, then the process is more complicated. Consider the matrix (0,0)(1,1)(2,1)(3,1)(2,0)(1,1)(2,1)(3,1). The process works as follows:
* First, ignore the second row, and only consider the first row. The first row of (0,0)(1,1)(2,1)(3,1)(2,0)(1,1)(2,1)(3,1) is 0,1,2,3,2,1,2,3.
* The "parent" of a number in the first row is defined as the rightmost column containing a lesser number. We start with the rightmost number, and repeatedly take the parent until we arrive at a 0 (which doesn't have a parent).
* The "ancestor" of a number in the first row is either its parent, or the parent of one of its ancestors (this is a recursive definition). The ancestors of the rightmost 3 in 0,1,2,3,2,1,2,3 are shown in bold:
** 0,1,2,3,2,1,2,3
* The next step is to restore the original matrix, and cross out any column which is not an ancestor of the rightmost number. Doing this gives us the following:
** (0,0)(1,1)(2,1)(3,1)(2,0)(1,1)(2,1)(3,1)
* Now, we ignore the first row, and only look at the second row. This gives the following:
** 0,1,1,1,0,1,1,1
* Note that we must remember which columns we removed in the earlier steps. The next step is to find the parent of the rightmost number (this is exactly what we did for PrSS), but now, we completely ignore any column which we removed. The resulting column is then the bad root.
* In our case, the rightmost number of 0,1,1,1,0,1,1,1 is 1, so we are looking for a 0, but the rightmost zero is crossed out, so we ignore it. The rightmost 0 which is not crossed out is at the very beginning of the expression.
Now that we have found the bad root column, the good and bad parts are found in the same way as PrSS. In the case of (0,0)(1,1)(2,1)(3,1)(2,0)(1,1)(2,1)(3,1), the bad root is (0,0), so the good part is empty and the bad part is (0,0)(1,1)(2,1)(3,1)(2,0)(1,1)(2,1).
The actual expansion is slightly different from PrSS. We have to take the good part, and concatenate it with m copies of the bad part, but this time we have to add a number to the first row of each bad part. Let "delta" be a number defined as the first row of the rightmost element, minus the first row of the bad root. In our case, delta is 3-0=3. When we concatenate the first copy of the bad part to the good part, we must add delta to the entire first row. In our case, we get (3,0)(4,1)(5,1)(6,1)(5,0)(4,1)(5,1). For the second copy of the bad part, we must add delta*2. We get (6,0)(7,1)(8,1)(9,1)(8,0)(7,1)(8,1). In general, for the k-th copy of the bad part, we must add delta*k.
Continue this for as many copies as necessary, and then concatenate them together. Finally, we arrive at the desired expansion:
(0,0)(1,1)(2,1)(3,1)(2,0)(1,1)(2,1)(3,0)(4,1)(5,1)(6,1)(5,0)(4,1)(5,1)(6,0)(7,1)(8,1)(9,1)(8,0)(7,1)(8,1)...
==Bashicu Matrix System==
It's finally time to learn the entirety of BMS. A matrix looks like this: (a,b,c...)(d,e,f...)(g,h,i...)... where a, b, c, d, e, f, g, h, i... are all non-negative integers. The columns can be any finite length.
If the rightmost column is all 0's, then just remove it. Otherwise, we have the following definitions:
We recursively define the "parent" of a number x in row n as follows:
* If n>1, then find all the ancestors of the number immediately above (recall the definition of "ancestor" from ear). Cross out any column which does not correspond to an ancestor. If n=1, then don't cross anything out.
* Ignore all rows in the matrix except for the n-th row. Find the rightmost number which is smaller than x and does not belong to a crossed-out column. This number is the parent of x.
We define the "bad root" of a matrix as the parent column of the last non-zero number in the rightmost column. The good and bad parts are found in the same way as the previous sections. 
Example: (0,0,0,0)(1,1,1,1)(2,2,2,1)(3,3,2,1)(4,3,2,0)(5,4,3,1)(4,2,2,1)(5,3,2,1)
In this matrix, the bad root is (0,0,0,0) (TODO: Go through step by step to show this)
Now, "delta" is no longer just a number, but it's an entire column. Subtract each number of the rightmost column with each number of the bad root to form this column. We get (5-0,3-0,2-0,1-0)=(5,3,2,1). To find delta, we have to subtract 1 from the last non-zero number in this column. So we get delta=(5,3,2,0).
In the expansion, when we are concatenating the n-th copy of the bad part, we have to add delta*n to each term. delta*n is defined as multiplying each term in delta by n.
In our example, the bad part is (0,0,0,0)(1,1,1,1)(2,2,2,1)(3,3,2,1)(4,3,2,0)(5,4,3,1)(4,2,2,1). When we concatenate the first copy of this to the good part, we have to add delta to it, giving (5,3,2,0)(6,4,3,1)(7,5,4,1)(8,6,4,1)(9,6,4,0)(10,7,5,1)(9,5,4,1). We can make another copy of the bad part, but adding delta*2=(10,6,4,0) instead of (5,3,2,0). The expansion is as follows:
* (0,0,0,0)(1,1,1,1)(2,2,2,1)(3,3,2,1)(4,3,2,0)(5,4,3,1)(4,2,2,1)(5,3,2,0)(6,4,3,1)(7,5,4,1)(8,6,4,1)(9,6,4,0)(10,7,5,1)(9,5,4,1)...
However, there is one final caveat to the expansion. When we are adding delta*n to a certain column in the bad part, we must first check each number in the column. If the bad root is one of the number's ancestors, then we add delta as normal, but if the bad root is not an ancestor, then we don't add delta to that number. For example, in (0,0,0)(1,1,1)(2,0,0)(1,1,1), the bad part is (0,0,0)(1,1,1)(2,0,0) and delta is (1,1,0). Normally, we would add delta to (2,0,0) when we add a new copy of the bad part, and in that case, the expansion would be (0,0,0)(1,1,1)(2,0,0)(1,1,0)(2,2,1)(3,1,0)(2,2,0)(3,3,1)(4,2,0)(3,3,0).... Indeed, the 2 in (2,0,0) does have the bad root as one of its ancestors, so that's fine. However, the middle 0 in (2,0,0) does not have any ancestors (because 0 is the smallest allowed number) so it certainly doesn't have the bad root as an ancestor. Thus, we don't add delta to this 0, but we do still add delta to the 2. The correct expansion is therefore (0,0,0)(1,1,1)(2,0,0)(1,1,0)(2,2,1)(3,0,0)(2,2,0)(3,3,1)(4,0,0)(3,3,0) (note how the numbers in bold differ from the previous [incorrect] expansion).
(TODO: Explain BM3.3 vs BM4)
Category:Introduction articles
Category:Bashicu matrix system