Bashicu matrix system | |
---|---|
Type | matrix |
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 OCF \(\psi\) and an unspecified system of fundamental sequences without a proof. 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 December 2019.
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, 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]}
Analysis of Growth Rate
The growth rate of 1-row matrices (aka the primitive sequence system) is \(f_{\varepsilon_0}(n)\)^{[25]} 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.^{[26]}^{[27]}^{[28]}^{[29]}^{[30]} 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
- ↑ Bashicu Matrix Calculator
- ↑ Fish "巨大数論発展の軌跡 (History of development of googology)" 現代思想 (Comtemporary philosophy) December 2019. pp. 19--28.
- ↑ Bashicu's GWiki account
- ↑ The summarization of the large numbers in BASIC language (Japanese article)
- ↑ Source code of Bashicu matrix calculator
- ↑ Definition of Bashicu Matrix by reading the source code
- ↑ User:Kyodaisuu/BasmatVersion
- ↑ The recent condition of Bashicu Matrix System (Japanese article)
- ↑ User_blog:Koteitan/Purely_mathematical_definition_of_BMS
- ↑ Proof that calculation of "standard form" Bashicu matrix terminates and copy
- ↑ BASIC program of Bashicu Matrix system
- ↑ explanation of the Bashicu matrix system (Japanese)
- ↑ Bashicu Matrix version 3
- ↑ BM3 has an infinite loop
- ↑ https://twitter.com/koteitan/status/1018931762053828608
- ↑ BM2 doesn't terminate.
- ↑ Bashicu Matrix version 4 complete analysis
- ↑ BM4=BM2.3
- ↑ 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
- ↑ https://docs.google.com/document/d/16aJKvY3HTsgBwP-FY9b1JkisvpKMiyCBPQtaAfXwEVs/edit
- ↑ Bashicu Matrix of the Cambrian Explosion
- ↑ The large number-finding thread 11.75: 152-155 and User:Kyodaisuu/BashicuProof
- ↑ Bashicu matrix proof of termination（in comment thread）
- ↑ Termination proof of the Pair sequence system
- ↑ A blog post introducing primitive sequence system
- ↑ Analysis of trio sequence system by Bashicu with his own ordinal notations
- ↑ Bashicu's calculation in more detail
- ↑ Analysis by KurohaKafka
- ↑ Analysis by Bubby3
- ↑ Analysis by Googleaarex
See also
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 Jason: Irrational arrow notation · δOCF · δφ
By mrna: SSAN · S-σ
By Nayuta Ito: N primitive
By Yukito: Hyper primitive sequence system · Y sequence · Y function
Indian counting system: Lakh · Crore · Uppala
Chinese, Japanese and Korean counting system: Wan · Yi · Zhao · Jing · Gai · Zi · Rang · Gou · Jian · Zheng · Zai · Ji · Gougasha · Asougi · Nayuta · Fukashigi · Muryoutaisuu
Buddhist text: Tallakshana · Dvajagravati · Mahakathana · Asankhyeya · Dvajagranisamani · Vahanaprajnapti · Inga · Kuruta · Sarvanikshepa · Agrasara · Uttaraparamanurajahpravesa · Avatamsaka Sutra · Nirabhilapya nirabhilapya parivarta
Other: Taro's multivariable Ackermann function · Sushi Kokuu Hen