This is the table of the rule sets of (almost) all sub versions of Bashicu Matrix invented in 2015-2018.

The aim of this entry is the comparison of the rule sets of them. The all sub versions can be categorized according to the difference of the three micro rules; Bad root searching rules, Bad part ascending rules and Ascension modification rules. In this article, the all sub versions are re-written in the mathematical definition with the same format. So that the comparison become easier. Please use this for your proof of the termination or analysis.

Here is the Japanese version of this article.

(25 Feb., 2019 Note) Recently, Bashicu fixed the latest definition as 'BM4'. If you want to know about the definition in the mathematical equations, please see this mine. If you want the original definition, see here.

Rule sets

Rule sets
Authors
Dates
Definitions Bad root searching Bad part ascending Ascension modification discussions
BM1
Bashicu
21,August'15
Left method All branches enabled No modify
rTSS
rpakr
25.March'18
Left method All branches enabled No modify same as trio sequence of BM1
BM1.1[1]
Bashicu
18,March'16
Upper-branch-ignoring-model All branches enabled No modify
BM2.1
koteitan
4.March'18
Upper-branch-ignoring-model All branches enabled No modify
Bubby3's fix
Bubby3
25,March'18
Upper-branch-ignoring-model All branches enabled No modify same as BM1.1
BM2
Bashicu
25,June'16
Upper-branch-ignoring-model BM2 based no modify analysing link(Bashicu, Deedlit11, 84.229.92.191, 77.127.67.249, KurohaKafka, Alemagno12, Googleaarex, Bubby3, rpakr)
BM4
Bashicu 1,Sep.'18
Upper-branch-ignoring-model Upper-branch-ignoring-model no modify
BM2.3
koteitan

Nish
Ecl1psed

18,Jun'18
Upper-branch-ignoring-model Upper-branch-ignoring-model no modify
BM3.1
Nish
18,July'18
Upper-branch-ignoring-model BM2-based all 1 or (\(a'_{xy}\),0,…,0)
  • Though its ascending rule is weaker than BM2, It is believed that it catch up BM2 and it is easy to analyze.
BM3.2
Nish
23,July'18
Upper-branch-ignoring-model Upper-branch-ignoring-model all 1 or (\(a'_{xy}\),…,0)
  • Though its ascending rule is weaker than BM4, it is easy to analyze.
BM3.1.1
Ecl1psed
20,July'18
Upper-branch-ignoring-model BM2-based all 1 or all 0
  • It can causes dangerous sequence as (2,0)(4,0) so that it is believed to be non-terminated.
BM3.3
rpakr Ecl1psed
22,June'19
Upper-branch-ignoring-model BM3.3 No modify
BM2.2
koteitan
8,March'18
Concestor method All branches enabled No modify
  • Analysis by Bubby3
  • Nish said \((0,0,0)(1,1,1)\) is weaker than \(\zeta_0\).
  • I made it by the changing bad root searching rule because I feel BM2's rule is complicating I should change the bad part ascending rule.

Settings

  • Bashicu matrix consist a matrix whose element is the natural number and a natural number named bracket.
  • The matrix \(\begin{pmatrix}c_{11}&c_{21}\\c_{12}&c_{22}\end{pmatrix}\) in the Bashicu matrix is often described as \((c_{11},c_{12})(c_{21},c_{22})\). In this page it is describe so.
  • \(f(n)\) is the function from a natural number into a natural number. in BM1, rTSS, BM1.1, Bubby3's fix, BM2 and BM4 \(f(n)\) is \(f(n)=n^2\), and in BM2.1, BM2.2, BM2.3 \(f(n)\) is \(f(n)=n+1\).

Common rules

A expansion procedure of a Bashicu matrix in a step is shown as below:

  1. Let the rightmost column \(C=(c_1, c_2, \cdots c_N)\).
  2. If the all elements of \(C\) are \(0\), The bad root is not found and the Jump to 5.
  3. Let the index of the lowermost non-zero element of the \(C\) be \(t\). (\(c_t\gt 0\land \forall k(k\gt t\rightarrow c_k=0)\))
  4. Decide the bad root \(R=(r_1, r_2, \cdots, r_N)\) by using the bad root searching rule of the rule set.
  5. remove the rightmost column \(C\).
  6. Replace \([n]\) into \([f(n)]\).
  7. If the bad root is not found, end the expansion procedure.
  8. let the bad root \(R\) and the partial matrix in the right side of it the bad part \(B=(b_{11},b_{12},\cdots,b_{1N})(b_{21},b_{22},\cdots,b_{1N})\cdots(b_{L1},b_{L2},\cdots,b_{LN})\).
  9. Before the bad root is copied,
    \(\Delta=(\delta_{11}, \cdots, \delta_{1N})\cdots(\delta_{L1},\cdots,\delta_{LN})\)is defined as ‘’the ascension level’’ as: \(\forall x~\delta_{xy}=\begin{cases}c_y-r_y&(y\lt t)\\0&(y \geq t)\end{cases}\).
  10. As the flag if the each elements of the bad part ascend or not, decide a pre-ascending matrix \(A'=(a'_{11}, a'_{12}, \cdots, a'_{1N})(a'_{21}, a'_{22}, \cdots, a'_{2N})\cdots(a'_{L1}, a'_{L2}, \cdots, a'_{LN})\) by using the bad part ascending rule of the rule set.
  11. By using the ascending modification rule of the rule set, decide an ascending matrix \(A\) from the pre-ascending matrix \(A'\).
  12. By using the value of the bracket \(n\), combine the \(B_1, B_2, \cdots, B_n\) which is defined as below into the right of the matrix.
  • \(B_1 = B + A \otimes \Delta\)
  • \(B_{k+1} = B_k + A \otimes \Delta\)
  • \(\otimes\) is the element-wise product as below:

\((a_{11},\cdots, a_{1N})\cdots(a_{L1},\cdots, a_{LN}) \otimes (b_{11},\cdots, b_{1N})\cdots(b_{L1},\cdots, b_{LN}) \)
\(= (a_{11}b_{11},\cdots, a_{1N}b_{1N})\cdots(a_{L1}b_{L1},\cdots, a_{LN}b_{LN})\) That's all.

After the repetitions of the expansion above, the value of the bracket when the matrix is empty is the large number.

Bad root searching rules

Left method

  1. If there exists a column \(M=(m_1, \cdots, m_N)\) which meets \(m_k \lt c_k\) in the row \(t\) and any upper row \(k \leq t\), and which is in the left side of \(c\), let the right side column for \(M=(m_1, \cdots, m_N)\) be the bad root \(R\). If it is not found, the bad root is not found.

Upper-branch-ignoring-model

  • the ancestor of the \(c\) is defined as \(c\) itself or the ancestor of the parent of \(c\) recursively.
  • the parent of the \(c\) is the rightmost element \(p\) which meets all of below recursively:
  1. \(p\) is in the same row of \(c\).
  2. \(p\) is in the left side of \(c\).
  3. \(p\) is smaller than \(c\).
  4. \(p\) is in the uppermost row, or \(p\) is in the same column as the ancestor of \(c'\). (\(c'\) is the element in the one row up of \(c\).)

Then, the bad root \(R\) is the column, in which there is the parent of the lowermost non-zero element of the rightmost column. If the parent is not found, the bad root is not found and end.


Concestor method

  • the ancestor of the \(c\) is defined as \(c\) itself or the ancestor of the parent of \(c\) recursively.
  • the parent of the \(c\) is the rightmost element \(p\) which meets all of below recursively:
  1. \(p\) is in the same row of \(c\).
  2. \(p\) is in the left side of \(c\).
  3. \(p\) is smaller than \(c\).

Then, the bad root \(R\) is the column, in which there is the parent of the lowermost non-zero element of the rightmost column. If the parent is not found, the bad root is not found and end.


bad part ascending rules

All branches enabled

  • \(\forall x,y(a'_{xy}=1)\)

BM2-based

The value of the ascension matrix \(a'_{xy}\) is defined as following.

\[p(x)=\max\left\{k|k \lt x \land b_{k1} \lt b_{x1}\right\}\] \[\forall y \left(a'_{1y}=1\right)\] \[\forall x\gt 1,~y \left(a'_{xy}=\begin{cases}1 & (\mathrm{if}~a'_{p(x)y}=1 \land b_{1y} \lt b_{xy})\\ 0 & \mathrm{otherwize}\end{cases}\right) \]

\(p(x)\) means the parent row of the column \(x\). It depends on only 1st row.

The second line means that the bad root is ascent anyway.

The third line means that the node \(b_{xy}\) is ascent only if the node in parent row of it is ascent and the value of \(b_{xy}\) is larger than bad root \(b_{1y}\).


Upper-branch-ignoring-model

  • the ancestor of the \(c\) is defined as \(c\) itself or the ancestor of the parent of \(c\) recursively.
  • the parent of the \(c\) is the rightmost element \(p\) which meets all of below recursively:
  1. \(p\) is in the same row of \(c\).
  2. \(p\) is in the left side of \(c\).
  3. \(p\) is smaller than \(c\).
  4. \(p\) is in the uppermost row, or \(p\) is in the same column as the ancestor of \(c'\). (\(c'\) is the element in the one row up of \(c\).)

For all \(x, y\) which meet \(r_y\) is the ancestor of \(b_{xy}\), \(a'_{xy}=1\), otherwise \(a'_{xy}=0\).



BM3.3

\begin{eqnarray} \mathrm{Ascension~matrix:}~a_{xy}&=&\left\{\begin{array}{ll} 1 &\Bigl(\mathrm{if}~ (y=t \land \exists i( r=(P_{y})^i(r+x))) \\ & ~~ ~\lor a_{xt}=1\\ & ~~ ~\lor (a_{(P_y(r+x)-r)y}=1 \land P_y(r+x)>r)\Bigr) \\ 0 &(\mathrm{otherwise}) \end{array}\right.\\ \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 i( p=(P_{y-1})^i(x))\} & (\mathrm{if}~y\gt 1)\\ \max\{p|p\lt x \land S_{py} \lt S_{xy} \} & (\mathrm{if}~y=1)\\ \end{array}\right.\\ \end{eqnarray} \(r \geq 1\) is the column index of the bad root. \(t \geq 1\) is the index of row in which there is the lowermost nonzero. \(S_{xy}\) is the element of the matrix in x th column and y th row. \((x,~y \geq 1)\)


Ascending modification rules

no modify

\(\forall xy (a_{xy}=a'_{xy})\)


All 1 or (\(a'_{x1}\),0,…,0)

For all \(x\), define \(a_{xy}\) from \(a'_{xy}\) as below:

  • If \(\forall y\leq t(a'_{xy}=1)\) then \(\forall y(a_{xy}=1)\) otherwise \(a_{x1}=a'_{x1}\) and \(\forall y\gt 1 \left(a_{xy}=0\right)\).

All 1 or All 0

For all \(x\), define \(a_{xy}\) from \(a'_{xy}\) as below:

  • if \(\forall y\leq t(a'_{xy}=1)\) then \(\forall x(a_{xy}=1)\), otherwise \(\forall y(a_{xy}=0)\).

Notes

  1. The rule doesn't have the formal name so that I named it as BM1.1 in this article.
Community content is available under CC-BY-SA unless otherwise noted.