Bashicu matrix system

Bashicu matrix system (BMS) is a notation designed to produce large numbers.Bashicu Matrix CalculatorFish, 巨大数論発展の軌跡 (History of development of googology), 現代思想 (Comtemporary philosophy) December 2019, pp. 19--28. It was invented by Bashicu in 2014.Bashicu's GWiki account There are several versions of definitions as explained in this article.
A Bashicu matrix is any rectangular matrix, such as
\[\begin{pmatrix}
a_{11} & a_{12} & a_{13}\\
a_{21} & a_{22} & a_{23}
\end{pmatrix}\]
with any dimensions, whose only elements are nonnegative integers. Such a matrix can also be expressed as the sequence of transposes of its columns (known as the sequence expression of a Bashicu matrix);
\[(a_{11},a_{21})(a_{12},a_{22})(a_{13},a_{23})\]
The function \(BM\) takes a natural number \(n\) along with a Bashicu matrix \(S\) as inputs and evaluates a natural number output, denoted as \(BM[n]\) or \(S[n]\), by repeatedly modifying the matrix until it's empty, following transformation rules explained in this article.
Using the FGH to approximate Bashicu matrix yields 1-row matrices (equivalent to the primitive sequence system) to be bounded by \(f_{\varepsilon_0}\) and 2-row matrices (aka the pair sequence system) by \(f_{\psi_0(\Omega_\omega)}\) with respect to Buchholz's function. The growth rate of matrices with 3 (trio sequence system) or more rows in general, and whether \(BM\) is always a total function, is an unsolved problem in mathematics.
== Definition ==
=== Original definition ===
Bashicu originally defined the system in Bashicu's undefined modification of the .The summarization of the large numbers in BASIC language (Japanese article) The program was not intended to actually be run because of the undefinedness of the modification of the language and also because the limit of the memory and calculation time does not allow calculating the actual final value of the large number in reality, and hence Fish wrote a program called "Bashicu matrix calculator" to demonstrate the intended calculation process (this program was verified by Bashicu). Therefore, the official definition of Bashicu matrices can be found in the source code of Fish's program.Source code of Bashicu matrix calculatorDefinition of Bashicu Matrix by reading the source code It can calculate BM1, BM2, BM2.1, BM2.2, BM2.3, BM3, BM3.1, BM3.2, and BM4 (these are explained in the "Revision" section of this article).User:Kyodaisuu/BasmatVersion
The Bashicu matrix calculator also has a web interface. It has 4 options of "incrementing n": the original definition for Bashicu matrices calls for "n=n * n", and the other options are variants. If the "Simulate Hardy function" variant is chosen, then the calculation exactly matches that of the Hardy function using the Wainer hierarchy for ordinals below \(\varepsilon_0\).
=== Transformation rules ===
The terms and rules below refer to the sequence expressions of matrices.
==== Terminology ====
* The "length" of a sequence is the number of pairs of brackets (i.e. the number of columns).
* An element of a sequence is a list nonnegative integers surrounded by just one pair of brackets.
* \(S\) denotes any sequence.
* \(Z\) denotes an element of the form \((0,0,...,0)\), which has one or more zeros.
* \(f(n) = n^2\). (variants of the notation may use other base functions)
* \(A\frown B\) is the concatenation of two sequences. For example, \((0,0)(1,1)\frown (2,2)(3,3)=(0,0)(1,1)(2,2)(3,3)\)
==== Calculation rules ====
Note: The calculation rule explained in the part is BM1 and it has a bug in which the calculation is not terminated. It was already updated into BM4. See "Definition with mathematical equations" below for the newest version.
Rule 1. \([n]=n\)
Rule 2. \(S Z[n]=S[f(n)]\)
Rule 3. If neither Rule 1 or 2 is applicable, apply the rules below in order.
Rule 3-1. Denote the i-th element from the left in \(S\) by \(S_i\) and the length of \(S\) by \(n\). That is, \(S=S_1S_2\cdots S_n\). Note that \(S_n\) is not equal to \(Z\) since Rule 2 is not applicable.
* If there is no element that is smaller than \(S_n\), replace \(S_n\) by \(Z\); \(S = S_1 S_2 \ldots S_{n-1} Z\) (and then apply Rule 2).
* If there is at least one element that is smaller than \(S_n\), let the rightmost one be \(S_i\). We define the good part of the sequence to be \(G = S_1 \ldots S_{i-1}\), the bad part of the sequence to be \(B = S_i \ldots S_{n-1}\), \(L = S_i\), and \(N = S_n\). Note that now \(S=G\frown B\frown N\).
Rule 3-2. From \(L = (L_0, L_1, \ldots ,L_m)\) and \(N = (N_0,N_1, \ldots ,N_m)\), \(\Delta=(\Delta_0,\Delta_1,\cdots\Delta_m)\) (difference) is calculated as:
* \(\Delta_i=0\) if there is a zero among \(N_0\) to \(N_{i+1}\) (letting \(N_{m+1}=0\))
* \(\Delta_i=N_i-L_i\) otherwise
As \(L < N\) by choice of \(L\), \(\Delta_i \ge 0\).
Rule 3-3: \(B(i)\) is defined as follows:
* \(B(0) = B\)
* \(B(i+1)\) is \(B(i) + \Delta\); here \(+\) means coordinate-wise addition of \(\Delta\) to every element of \(B(i)\). For example, when \(B(0) = (1,1,1)(2,2,2)(3,3,3)\) and \(\Delta = (3,1,0)\), we have \(B(1) = (4,2,1)(5,3,2)(6,4,3)\) and \(B(2) = (7,3,1)(8,4,2)(9,5,3)\).
Rule 3-4: \(S[n] = \{ G \frown B(0) \frown B(1) \frown \ldots\ \frown B(f(n))\}[f(n)] \)
=== Definition with mathematical equations ===
Koteitan showedThe recent condition of Bashicu Matrix System (Japanese article)User_blog:Koteitan/Purely_mathematical_definition_of_BMS we could also define Bashicu Matrix Number as following \(K\), using these rules. \(\mathrm{expand}()\) in the rule is based on the version BM4.
\begin{eqnarray*}
\mathrm{Number:}~K&=&\mathrm{Bm}^{10}(9)\\
\mathrm{Function:}~\mathrm{Bm}(n)&=&\mathrm{expand}((\underbrace{0,0,\cdots,0}_{n+1})(\underbrace{1,1,\cdots,1}_{n+1})[n])\\
\mathrm{Rule:}~\mathrm{expand}([n])&=&n\\
\mathrm{expand}({\boldsymbol S}[n])&=&\left\{\begin{array}{ll}
\mathrm{expand}({\boldsymbol S}_0\cdots{\boldsymbol S}_{X-2}[f(n)])&(\mathrm{if}~\forall y~S_{(X-1)y}=0)\\
\mathrm{expand}({\boldsymbol G}{\boldsymbol B}^{(0)}{\boldsymbol B}^{(1)}{\boldsymbol B}^{(2)} \cdots {\boldsymbol B}^{(f(n))}[f(n)])&(\mathrm{otherwise})\\
\end{array}\right.\\
\mathrm{Activation~function:}~f(n)&=&n^2\\
\mathrm{Matrix:}~{\boldsymbol S}&=&{\boldsymbol S}_0{\boldsymbol S}_1\cdots{\boldsymbol S}_{X-1}\\
\mathrm{Vector:}~{\boldsymbol S}_x&=&(S_{x0},S_{x1},\cdots,S_{x(Y-1)})\\
\mathrm{Good~part:}~{\boldsymbol G}&=&{\boldsymbol S}_0{\boldsymbol S}_1\cdots{\boldsymbol S}_{r-1}\\
\mathrm{Bad~part:}~{\boldsymbol B}^{(a)}&=&{\boldsymbol B}_0^{(a)}{\boldsymbol B}_1^{(a)}\cdots{\boldsymbol B}_{X-2-r}^{(a)}\\
{\boldsymbol B}_x^{(a)}&=&(B_{x0}^{(a)},B_{x1}^{(a)},\cdots,B_{x(Y-1)}^{(a)})\\
B_{xy}^{(a)}&=&S_{(r+x)y}+a\Delta_{y}A_{xy}\\
\mathrm{Ascension~offset:}~\Delta_{y}&=&\left\{\begin{array}{ll}
S_{(X-1)y}-S_{ry}&(\mathrm{if}~y\lt t)\\
0 &(\mathrm{if}~y\geq t)
\end{array}\right.\\
\mathrm{Ascension~matrix:}~A_{xy}&=&\left\{\begin{array}{ll}
1 &(\mathrm{if}~ \exists a( r=(P_{y})^a(r+x)))\\
0 &(\mathrm{otherwise})
\end{array}\right.\\
\mathrm{Lowermost~nonzero:}~t&=&\max\{y|S_{(X-1)y}\gt 0\}\\
\mathrm{Bad~root:}~r &=& P_t(X-1)\\
\mathrm{parent~of}~S_{xy}:~P_{y}(x)&=&\left\{\begin{array}{ll}
\max\{p|p\lt x \land S_{py} \lt S_{xy} \land \exists a( p=(P_{y-1})^a(x))\} & (\mathrm{if}~y\gt 0)\\
\max\{p|p\lt x \land S_{py} \lt S_{xy} \} & (\mathrm{if}~y=0)\\
\end{array}\right.\\
\end{eqnarray*}
== Calculation Example ==
Let's look at the first expansion step of \((0,0,0)(1,1,1)(2,2,2)(3,3,3)(4,2,0)[2]\) using the instructions above:
\begin{eqnarray*}{\boldsymbol S} &=& {\boldsymbol S}_0{\boldsymbol S}_1{\boldsymbol S}_2{\boldsymbol S}_3{\boldsymbol S}_4\\
&=&(S_{00},S_{01},S_{02})(S_{10},S_{11},S_{12})(S_{20},S_{21},S_{22})(S_{30},S_{31},S_{32})(S_{40},S_{41},S_{42})\\
&=&(0,0,0)(1,1,1)(2,2,2)(3,3,3)(4,2,0)
\end{eqnarray*}
* Parent of the first row: The rightmost element which is smaller than the last entry in the 1st row is called the parent of the 1st row. In this example, the last entry is \(S_{40} = 4\) and the parent is \(S_{30}=3\). The column which includes the parent of \(S_{xy}\) is represented as \(P_y(x)\) (note that it refers to the column index, not the entry itself).
* Ancestors: The ancestors of an element are the element itself and its ancestor’s parents, recursively. In this case, the ancestors of \(S_{40} = 4\) are \(S_{40}=4,~S_{30}=3,~S_{20}=2,~S_{10}=1~and~S_{00}=0\).
* Parents in the second and lower rows: For any element \(S_{xy}\) not in the first row, its parent is defined as the rightmost element which is both:
** in the same column as one of the upper element \(S_{x,y-1}\)'s ancestors, \((P_{y-1})^a(x)\)
** smaller than and to the left of \(S_{xy}\)
* bad root: The column \(P_t(X-1)\) which has the parent of the rightmost column \(X-1\) of the lowermost nonzero row \(t\) is called the bad root. The bad root marks the boundary between the non-copied part of the matrix (known as the good part \({\boldsymbol G}\)) and the part of the matrix to be copied (the bad part \({\boldsymbol B}^{(0)}\)). In this case, \(S_{41} = 2\) is the lowermost nonzero entry in the rightmost column, and its parent is \(S_{11}=1\), so the bad root of this matrix is the second column (\(r=1\)).
* Good Part and Bad part: \({\boldsymbol S}_r = (1,1,1)\) means that \({\boldsymbol G} = (0,0,0)\) and \({\boldsymbol B}^{(0)} = (1,1,1)(2,2,2)(3,3,3)\).
* Ascension Offset: Using the value of the bad root \({\boldsymbol S}_r = (1,1,1)\) and the value of cut children \({\boldsymbol S}_{X-1} = (4,2,0)\), the ascension offset is calculated as \((\Delta_0, \Delta_1, \Delta_2) = (3,0,0)\).
* Ascension Matrix: The Ascension Matrix has the value 1 if the corresponding entry in \(S\) has the bad root as one of its ancestors, and 0 if not. In this case, we get \(A_{xy}=(1,1,1)(1,1,1)(1,1,1)\).
* Copying the Bad Part: Finally, the modified copies of the bad part \({\boldsymbol B}^{(a)}\) become \({\boldsymbol B}^{(0)} = (1,1,1)(2,2,2)(3,3,3)\), \({\boldsymbol B}^{(1)} = (4,1,1)(5,2,2)(6,3,3)\), \({\boldsymbol B}^{(2)} = (7,1,1)(8,2,2)(9,3,3)\), \({\boldsymbol B}^{(3)} = (10,1,1)(11,2,2)(12,3,3)\) and \({\boldsymbol B}^{(4)} = (13,1,1)(14,2,2)(15,3,3)\), respectively.
* Expansion rule: According to the Expansion rule, we get \({\boldsymbol S}[2] = {\boldsymbol G}{\boldsymbol B}^{(0)}{\boldsymbol B}^{(1)}{\boldsymbol B}^{(2)}{\boldsymbol B}^{(3)}{\boldsymbol B}^{(4)}[4]\) and so (0,0,0)(1,1,1)(2,2,2)(3,3,3)(4,2,0)[2] = (0,0,0)(1,1,1)(2,2,2)(3,3,3)(4,1,1)(5,2,2)(6,3,3)(7,1,1)(8,2,2)(9,3,3)(10,1,1)(11,2,2)(12,3,3)(13,1,1)(14,2,2)(15,3,3)[4]. As a proper matrix, the final expansion after one step looks like this:
\[\begin{pmatrix}
0 & 1 & 2 & 3 & 4\\
0 & 1 & 2 & 3 & 2\\
0 & 1 & 2 & 3 & 0\\
\end{pmatrix}[2] =
\begin{pmatrix}
0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15\\
0 & 1 & 2 & 3 & 1 & 2 & 3 & 1 & 2 & 3 & 1 & 2 & 3 & 1 & 2 & 3 \\
0 & 1 & 2 & 3 & 1 & 2 & 3 & 1 & 2 & 3 & 1 & 2 & 3 & 1 & 2 & 3 \\
\end{pmatrix}[4]\]
This result matches the calculation result by the Bashicu matrix calculator.
== Termination and Revisions ==
The first question after the creation of BM1 was whether the calculation would always terminate. This went unanswered until User:KurohaKafka posted a supposed proof of termination on the Japanese BBS 2ch.net in 2016.Proof that calculation of "standard form" Bashicu matrix terminates and copy However, User:Hyp cos disproved it in the talk page of this very article by showing a non-teminating sequence, suggesting that the 2016 proof was incorrect.Something wrong happensBashicu matrix proof of termination（in comment thread） It is still unknown whether the Bashicu Matrix System always terminates as of September 2020.
Consequently, Bashicu updated the system by making Bashicu Matrix version 2 (BM2), implemented as another algorithm in BASIC.BASIC program of Bashicu Matrix system BashicuHyudora provided a slide to explain its new expansion rule.explanation of the Bashicu matrix system (Japanese) Bashicu again updated the definition to BM3 on June 12th, 2018.Bashicu Matrix version 3 Unfortunately, User:Alemagno12 showed that there was a non-terminating example in BM3 later that month.BM3 has an infinite loop
In November 11th, 2018, a Japanese Googology Wiki user P進大好きbot provided a termination proof of pair sequence systems, a special case of Bashicu matrices where the number of the rows is exactly 2.p進大好きbot, ペア数列の停止性, Japanese Googology Wiki user blog. 
Koteitan proposed another way to fix BM2 on his twitter and implemented it as a C program; this version is known as BM2.3. He also showed that the particular matrix (0,0,0,0)(1,1,1,1)(2,2,1,1)(3,3,1,1)(4,2,0,0)(5,1,1,1)(6,2,1,1)(7,3,1,1) expands differently between BM2 and BM2.3.https://twitter.com/koteitan/status/1018931762053828608 On August 28th, Bubby3 confirmed that BM2 indeed doesn't terminate with that same matrix.BM2 doesn't terminate.
Bashicu finally fixed the official definition, yielding BM4. This is the latest version as of September 1st, 2018. Koteitan has analysed the codeBashicu Matrix version 4 complete analysis and stated that the behavior of BM4 is identical to that of BM2.3.BM4=BM2.3
Though the last official revision by Bashicu is BM4, a handful of unofficial variants, such as BM2.2, BM2.5, BM2.6, BM3.1, BM3.1.1, BM3.2, and PsiCubed2's version, have been proposed.The recent condition of Bashicu Matrix System (Japanese article) introduces the blog post A list of all BMS versions and their differences and My own version of BMS To recap, versions of Bashicu matrix followed by whole numbers (namely, 1-4) were defined by Bashicu themselves and all other versions were made by others.
The latest proposals are called Idealized BMShttps://docs.google.com/document/d/16aJKvY3HTsgBwP-FY9b1JkisvpKMiyCBPQtaAfXwEVs/edit and consist of several new and/or changed rules, depending on the version:
(Mar.19(1), Mar.19(2), BR+delta comp, UBRABC, UBRABC+parent check, UBRA+parent check, Rpakr Def.1, Def.2, Def.3, Def.4 and Def.5).Bashicu Matrix of the Cambrian Explosion
== As Notations of Ordinals ==
Bashicu matrix system is not an ordinal notation system, because a recursive well-ordering on the system is not defined. However, it is strongly believed that it can "express" ordinals in the way explained in the article of fundamental sequences. More precisely, it is believed that there is a map \(o\) from standard Bashicu matricesFish. User blog:Kyodaisuu/Standard Bashicu matrix 2023-09-08. \(M\) with respect to a given version (which has not been known to have infinite loops) to countable ordinals such that \(o((0)) = 0\) and for any standard Bashicu matrix \(S \neq (0)\), \(o(S)\) is the least ordinal greater than \(o(S^{(n)})\) for any \(n \in \mathbb{N}\), where \(S^{(n)}\) denote the standard matrix given as the single "expansion" of \(S[n]\).
The existence of such a map \(o\) implies the termination of the corresponding version, and hence has not been verified yet in a peer-reviewed source, although there have been many who claim to have proven the termination For a standard Bashicu matrix \(S\), we call \(o(S)\) the ordinal corresponding to \(S\). Bashicu coined the ordinals corresponding to several standard Bashicu matrices with respect to BM4.Bashicu, バシク行列の解析, Japanese Googology Wiki user blog, retrieved at 02/07/2020.
standard Bashicu matrix \(S\) 	name of the corresponding ordinal \(o(S)\)
\((0,0,0)(1,1,1)(2,2,0)\) 	first back gear ordinal
\((0,0,0)(1,1,1)(2,2,1)(3,3,0)\)	second back gear ordinal
\((0,0,0)(1,1,1)(2,2,2)\) 	omega back ordinal
== Analysis of Growth Rate ==
The growth rate of 1-row matrices (aka the primitive sequence system) is \(f_{\varepsilon_0}(n)\)A blog post introducing primitive sequence system and the growth rate of 2-row matrices (the pair sequence system) is \(f_{\psi_0(\Omega_\omega)}(n)\) with respect to Buchholz's function in BM4.
A complete analysis of the growth rate of matrices with 3 (trio sequence system) or more rows is difficult because the system is so strong. People are analyzing the system to some extent.Analysis of trio sequence system by Bashicu with his own ordinal notationsBashicu's calculation in more detailAnalysis by KurohaKafkaAnalysis by Bubby3Analysis by Googleaarex Unfortunately, many of the analyses are not reproducible, because they include results which are described in terms of unspecified or ill-defined OCFs such as Bashicu's OCF and UNOCF.
Most claims about the strength and well-foundedness of BMS have so far not been formally defined, or they haven't been proven. For example, all analyses past the matrix
\[\begin{pmatrix}
0 & 1 \\
0 & 1 \\
0 & 1
\end{pmatrix}\]
contain no proof of correctness. The furthest analysis which specifies an algorithm to convert matrices to ordinals, claims that the matrix
\[\begin{pmatrix}
0 & 1 & 2 & 3 & 2 \\
0 & 1 & 1 & 1 & 0 \\
0 & 1 & 1 & 0 & 0
\end{pmatrix}\]
corresponds to the countable limit of extended Buchholz's function in BM4, although no proof exists yet.User_blog:Ytosk/Algorithm_that_changes_BMS_matrices_into_ordinals_up_to_SRO
Many explicitly written analyses past the above matrix are (usually extremely long) lists of correspondences between matrices and ordinals that lack an algorithm for converting matrices to ordinals. In order to verify the correctness of the correspondences, it is insufficient to observe finitely many small examples. Since the tables are created just by observing small values and expecting that the same pattern holds for more complicated matrices without a proof, they do not give valid evidences of the correspondences. In particular, they do not imply the termination of the Bashicu matrix system. Thus, these analyses should only be treated as lists of conjectures that convey a certain amount of intuition, yet lack an explicit proof strategy. Furthermore, some "analysis" goes far beyond the limit of existing OCFs, or use an unspecified (and perhaps ill-defined) OCF. Thus, they are not even well-defined mathematical conjectures, but rather only heuristic arguments.
Here are some conjectures for the corresponding ordinal of certain matrices:
Matrix 	Ordinal + Explanation
\[\begin{pmatrix} 0 & 1 & 2 & 3 \\ 0 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 \end{pmatrix}\] 	It is believed to correspond to \(\psi(I_\omega)\) with respect to certain OCFs. Unfortunately, this conjecture is often stated with no specification of the OCF being used which are sometimes unspecified or ill-defined. As said before, there is no proof or algorithm to support this result.
\[\begin{pmatrix} 0 & 1 & 2 & 3 & 3 \\ 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 \end{pmatrix}\]	It is believed to correspond to \(\psi(M_\omega)\) with respect to certain OCFs. The same situation as described above occurs here and below as well.
\[\begin{pmatrix} 0 & 1 & 2 & 3 & 4 \\ 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 \end{pmatrix}\]	It is believed to correspond to \(\psi(K_\omega)\) with respect to certain OCFs.
Futhermore, Bashicu has described the ordinal corresponding to
\[\begin{pmatrix}
0 & 1 \\
0 & 1 \\
0 & 1 \\
0 & 1
\end{pmatrix}\]
with respect to a version called BM4, by one of his original OCFs (which is not formally defined). Of course, the termination of BM4 up to that matrix (or even much smaller 3-row matrix) is still an open problem.
The ordinal in FGH approximating the growth of an n-row matrix in the form
\[\begin{pmatrix}
0 & 1 \\
0 & 1 \\
\vdots & \vdots \\
0 & 1
\end{pmatrix}\]
for \(n\ge4\) is not yet known or even has a widely accepted conjectured value, and its well-definedness is even unknown.
All functions definable by BMS are computable (if they are total), and therefore much weaker than the busy beaver function, \(\Sigma(n)\), and the other uncomputable functions.
== Footnotes ==
== Sources ==
== See also ==
* Blog posts about Bashicu matrix system
ja:バシク行列システム
zh:Bashicu矩陣系統
fr:Système de matrice de Bashicu
 
Category:Googology in Asia
Category:Eponymous functions
Category:Notations
Category:Higher computable level
Category:Unsolved problems
Category:Numbers by Bashicu