Diagram visualization of BMS

Expansion example of Bashicu matrix system

Bashicu matrix system
Typematrix
Based on\(n^2\)
Growth rate\(f_{>\psi(\psi_{I_\omega}(0))}(n)\)

Bashicu matrix system is a notation designed to produce large numbers.[1][2] It was invented by Bashicu in 2014.[3]

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(\Omega_\omega)}\) with respect to Buchholz's function. Analysis of 3-row matrices is ongoing without a proof, but the matrix

\[\begin{pmatrix} 0 & 1 & 2 & 3 \\ 0 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 \end{pmatrix}\] is believed to correspond to a total computable function bounded by \(f_{\psi(\psi_{I_\omega}(0))}\) with respect to an unspecified (and perhaps ill-defined) OCF \(\psi\) and an unspecified (and perhaps ill-defined) system of fundamental sequences without a proof. Since the "analysis" is based on an unspecified OCF without a fixed precise definition, the estimation is not so meaningful in the sense that we cannot argue on the correctness. Moreover, almost all "analyses" of Bashicu matrix system are given by showing tables including tens or hundreds of lines of the correspondences from Bashicu 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. For example, 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, which will be explained later, by one of his original OCFs without specific definitions, but 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}\] is not yet known, and its well-definedness is even unknown. The corresponding function is possibly weaker than Loader's function even if it is total.

Definition

Original definition

Bashicu originally defined the system in the BASIC programming language.[4] The program was not intended to actually be run, so Fish wrote a program called "Bashicu matrix calculator" to demonstrate the 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.[5][6] 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).[7]

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\).

Notation

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. If the growth rate of \(BM[n]\) can be approximated in the Hardy hierarchy by a function with an ordinal index \(\alpha\), then we say the matrix \(S\) represents the ordinal \(\alpha\). For example:

\[\begin{pmatrix} 0 & 1 & 2 & 3 & 3\\ 0 & 1 & 2 & 3 & 2 \end{pmatrix} = (0,0)(1,1)(2,2)(3,3)(3,2)\]

represents \(\psi_0(\Omega_3+\psi_2(\Omega_3 + \Omega_2))\) with respect to Buchholz's function.

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 showed[8][9] 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, its parent, and its parent'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.[10] 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. Consequently, Bashicu updated the system by making Bashicu Matrix version 2 (BM2), implemented as another algorithm in BASIC.[11] BashicuHyudora provided a slide to explain its new expansion rule.[12]

Bashicu again updated the definition to BM3 on June 12th, 2018.[13] Unfortunately, User:Alemagno12 showed that there was a non-terminating example in BM3 later that month.[14]

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.[15] On August 28th, Bubby3 confirmed that BM2 indeed doesn't terminate with that same matrix.[16]

Bashicu finally fixed the official definition, yielding BM4. This is the latest version as of September 1st, 2018. Koteitan has analysed the code[17] and stated that the behavior of BM4 is identical to that of BM2.3.[18]

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.[19] 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 BMS[20] 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).[21]

More about Termination

It is still unknown whether the Bashicu Matrix System always terminates as of September 2020.

An article proving termination in a particular case was posted by KurohaKafka in 2016.[22] However, later analysis showed that the proof was wrong.[23]

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.[24]

As Notations of Ordinals

Although Bashicu matrix system is not an ordinal notation system, 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 matrices \(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. 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.[25]

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)\)[26] and the growth rate of 2-row matrices (the pair sequence system) is \(f_{\psi(\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.[27][28][29][30][31] 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.

All functions definable by BMS are computable and therefore much weaker than the busy beaver function, \(\Sigma(n)\), and the other uncomputable functions even if they are total .

Sources

  1. Bashicu Matrix Calculator
  2. Fish, 巨大数論発展の軌跡 (History of development of googology), 現代思想 (Comtemporary philosophy) December 2019, pp. 19--28.
  3. Bashicu's GWiki account
  4. The summarization of the large numbers in BASIC language (Japanese article)
  5. Source code of Bashicu matrix calculator
  6. Definition of Bashicu Matrix by reading the source code
  7. User:Kyodaisuu/BasmatVersion
  8. The recent condition of Bashicu Matrix System (Japanese article)
  9. User_blog:Koteitan/Purely_mathematical_definition_of_BMS
  10. Proof that calculation of "standard form" Bashicu matrix terminates and copy
  11. BASIC program of Bashicu Matrix system
  12. explanation of the Bashicu matrix system (Japanese)
  13. Bashicu Matrix version 3
  14. BM3 has an infinite loop
  15. https://twitter.com/koteitan/status/1018931762053828608
  16. BM2 doesn't terminate.
  17. Bashicu Matrix version 4 complete analysis
  18. BM4=BM2.3
  19. 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
  20. https://docs.google.com/document/d/16aJKvY3HTsgBwP-FY9b1JkisvpKMiyCBPQtaAfXwEVs/edit
  21. Bashicu Matrix of the Cambrian Explosion
  22. The large number-finding thread 11.75: 152-155 and User:Kyodaisuu/BashicuProof
  23. Bashicu matrix proof of termination(in comment thread)
  24. p進大好きbot, ペア数列の停止性, Japanese Googology Wiki user blog.
  25. Bashicu, バシク行列の解析, Japanese Googology Wiki user blog, retrieved at 02/07/2020.
  26. A blog post introducing primitive sequence system
  27. Analysis of trio sequence system by Bashicu with his own ordinal notations
  28. Bashicu's calculation in more detail
  29. Analysis by KurohaKafka
  30. Analysis by Bubby3
  31. Analysis by Googleaarex

See also

Googology in Asia

Fish numbers: Fish number 1 · Fish number 2 · Fish number 3 · Fish number 4 · Fish number 5 · Fish number 6 · Fish number 7
Mapping functions: S map · SS map · S(n) map · M(n) map · M(m,n) map
By Aeton: Okojo numbers · N-growing hierarchy
By BashicuHyudora: Primitive sequence number · Pair sequence number · Bashicu matrix system
By 巨大数大好きbot: Flan numbers
By Jason: Irrational arrow notation · δOCF · δφ · ε function
By mrna: 段階配列表記 · SSAN · S-σ
By Nayuta Ito: N primitive
By p進大好きbot: Large Number Garden Number
By Yukito: Hyper primitive sequence system · Y sequence · YY sequence · Y function
Indian counting system: Lakh · Crore · Tallakshana · Uppala · Dvajagravati · Mahakathana · Asankhyeya · Dvajagranisamani · Vahanaprajnapti · Inga · Kuruta · Sarvanikshepa · Agrasara · Uttaraparamanurajahpravesa · Avatamsaka Sutra · Nirabhilapya nirabhilapya parivarta
Chinese, Japanese and Korean counting system: Wan · Yi · Zhao · Jing · Gai · Zi · Rang · Gou · Jian · Zheng · Zai · Ji · Gougasha · Asougi · Nayuta · Fukashigi · Muryoutaisuu
Other: Taro's multivariable Ackermann function · TR function · Sushi Kokuu Hen

Community content is available under CC-BY-SA unless otherwise noted.