Introduction To Bashicu Matrix System

It's been quite a while and I'm back with BM2!

Because Bashicu Matrix System is very difficult, so I will explain it.

(note: this article is from Japanese wiki)

Definitions of notations

Bashicu Matrix looks like this:

(0,0)(1,1)(2,2)(3,3)(3,2)[8]

Generally, there are finite pairs of brackets, which have finite whole numbers, followed by a number in square brackets.

Definitions of words

• The length of a sequence is the number of pairs of brackets.

  The matrix above has the length of 5.

• A sequence which has the length of 1 (or have one pair of brackets) is called the element of the sequence.
• S is an sequence.
• Z is (0,0,...,0), which has one or more zeros.
• f(n) is n squared. (You can change this rule, but it's considered as a variant)
• A+B is connection of sequence.

  For example, (0,0)(1,1)+(2,2)(3,3)=(0,0)(1,1)(2,2)(3,3)

• how to compare elements:

As for $A = (a_0,a_1,...,a_m), B = (b_0,b_1,...,b_m), D=\{ 0,1,...,m \}$,

$A < B \Leftrightarrow \forall i \in D ((a_i<b_i) \vee \exists j \in D (b_j=0 \wedge j \le i))$

In English, As for the least j which meets $b_j = 0$ (j=m+1 if such j does not exist), $A < B$ if all of $a_1 < b_1, a_2 < b_2, ... , a_{j-1} < b_{j-1}$ is true. And, there is no definition for A>B, so you can define only "smaller" or not. Even if A in smaller than B, B is not always "bigger" than A.

Here are simpler words: Compare A and B from the left to the light until you find a zero in B. If numbers from B is always bigger, $A < B$.If not, A is not smaller than B. (If you find zero in B at the first number, A is smaller.)

Examples:

I will use N for "not smaller".
(1,0)<(2,1) //compare 1,2 and 0,1
(3,5)N(1,2) //it is obvious that (3,5)>(1,2), but "bigger" is not defined.
(0,2)<(1,0) //compare 0,1 because second number in B is zero
(5,9)<(0,32) //first zero in B makes bigger than anything
(0,2)N(2,1) //because 0<2 but 2>1
(1,3,0)<(2,0,0) //compare only 1,2
(1,3,0)N(2,2,0) //you also have to compare 3,2
(1,3,0)<(2,4,0) //because 1<2 and 3<4
(1,3,100,googol)<(2,4,0,googolplex) //do not compare after the first zero in B

How to calculate BM1

• Rule 1. [n]=n

  It means that if there are no brackets, the number in the square brackets is the answer.

• Rule 2. S Z[n]=S[f(n)]

  It means that if the last bracket contain only zeroes, remove it and change n into [n].

• (Rule 3 is for comparison of elements)
• Rule 4. if neither Rule 1 and 2 is applicable, call the i-th element from the left in S $S_i$. Now, $S=S_1S_2\cdots S_n$.

  Rule 4-1. Let's call the last element $S_n$. It must be not Z because Rule 2 is applicable if S_n is Z.

  Rule 4-1-1. If there is no element that is smaller than $S_n$, change $S_n$ into Z (and calculate it with Rule 2).

  Rule 4-1-2. If there is at least one element that is smaller than $S_n$, let's call the rightmost one $S_i$. Now, suppose $G$ is everything before $S_i$ (excluding $S_i$), $B$ is everything between $S_i$ and $S_n$ (including $S_i$ and excluding $S_n$), $P$ is $S_n$. (Now, S is G and B and P combined.) And continue to Rule 4-2 through 4-4.

• Rule 4-2. You calculate $\Delta$ here. (It's P in Japanese Wiki, but I use delta because it means "difference")

  I will name each number in L(S_i in Rule 4-1) and S_n and delta: $L=(L_0,L_1,\cdots L_m),S_n=(N_0,N_1,\cdots N_m),\Delta=(\Delta_1,\Delta_2,\cdots\Delta_m)$, and suppose $\Delta_{m+1}=0$.

  Then, $\Delta_i=0$ if there is 0 in N_0 to N_(i+1), $\Delta_i=N_i-L_i$ else.

  (Note: $\Delta_i$ must be a whole number)

• Rule 4-3. You calculate $B(i)$ here.

  $B(0)=B$

  B(i+1) is B(i) add delta. In this case, "add" means the addition of numbers in brackets.

  For example:

If B=(1,1,1)(2,2,2)(3,3,3) and delta=(3,1,0),
B(0)=(1,1,1)(2,2,2)(3,3,3)
B(1)=(4,2,1)(5,3,2)(6,4,3)
B(2)=(7,3,1)(8,4,2)(9,5,3)
and so on.

• Rule 4-4.$S[n]=G+B(0)+B(1)+\cdots+B(f(n))[f(n)]$

Take free examples until you understand! (BM1)

#1.(0,0,0)(1,1,1)(2,2,2)(3,3,3)(4,2,0)[2]
f(n)=4
G=(0,0,0),B=(1,1,1)(2,2,2)(3,3,3),P=(4,2,0) //(1,1,1)<(4,2,0)
Δ=(3,0,0) //P=(4,2,0) and L=(1,1,1)
B(0)=(1,1,1)(2,2,2)(3,3,3)
B(1)=(4,1,1)(5,2,2)(6,3,3)
B(2)=(7,1,1)(8,2,2)(9,3,3)
B(3)=(10,1,1)(11,2,2)(12,3,3)
B(4)=(13,1,1)(14,2,2)(15,3,3)
Therefore, (0,0,0)(1,1,1)(2,2,2)(3,3,3)(4,2,0)[2] changes into
(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]

#2 (0,0,0)(1,1,1)(2,2,2)(3,3,3)(4,2,1)[2]
f(n)=4
G=nothing,B=(0,0,0)(1,1,1)(2,2,2)(3,3,3),P=(4,2,1) //(1,1,1)N(4,2,1) and (0,0,0)<(4,2,1)
Δ=(4,2,0) // P=(4,2,1) and L=(0,0,0)
B(0)=(0,0,0)(1,1,1)(2,2,2)(3,3,3)
B(1)=(4,2,0)(5,3,1)(6,4,2)(7,5,3)
B(2)=(8,4,0)(9,5,1)(10,6,2)(11,7,3)
B(3)=(12,6,0)(13,7,1)(14,8,2)(15,9,3)
B(4)=(16,8,0)(17,9,1)(18,10,2)(19,11,3)
Therefore, (0,0,0)(1,1,1)(2,2,2)(3,3,3)(4,2,1)[2] changes into
(0,0,0)(1,1,1)(2,2,2)(3,3,3)(4,2,0)(5,3,1)(6,4,2)(7,5,3)(8,4,0)(9,5,1)(10,6,2)(11,7,3)(12,6,0)(13,7,1)(14,8,2)(15,9,3)(16,8,0)(17,9,1)(18,10,2)(19,11,3)[4]

#3.(1,1,1)(1,1,1)(2,2,2)(3,3,3)(4,2,1)[2]
f(n)=4
There is no S_i
Therefore, (1,1,1)(1,1,1)(2,2,2)(3,3,3)(4,2,1)[2] changes into
(1,1,1)(1,1,1)(2,2,2)(3,3,3)(0,0,0)[2] //by RUle 4-1-1

#4.(0)(0)(1)(2)(1)[2]
f(n)=4
G=(0),B=(0)(1)(2),P=(1)
Δ=(0) //delta is always zero if each bracket have only one number
B(0)=(0)(1)(2)
B(1)=(0)(1)(2)
B(2)=(0)(1)(2)
B(3)=(0)(1)(2)
B(4)=(0)(1)(2)
Therefore, (0)(0)(1)(2)(1)[2] changes into
(0)(0)(1)(2)(0)(1)(2)(0)(1)(2)(0)(1)(2)(0)(1)(2)(0)(1)(2)[4]

(more to come)

comparison to Hierarchy

Now, let's consider the Bashicu hierarchy:

$B_0(x)=x$

$B_{\alpha+1}(x)=B_{\alpha}(x^2)$

$B_{\alpha}(x)=B_{\alpha[x^2]}(x^2)$

This hierarchy matches Bashicu Matrix System very well.

The first rule means Rule 1 (rule for nothing before [n]), regarding nothing as zero.

The second rule means Rule 2 (rule for the last bracket containing only zeroes), regarding (0) as a successor.

The third rule means Rule 4 (the most common rule), but it's difficult to explain. First, all x turned into x^2, which means f(n) in definition of Bashicu Matrix System. Next, what is "fundamental sequence" of a matrix if it is an ordinal?

It's simple. When a matrix is calculated, a part of it is copied and the whole thing gets longer. For example:

(0)(1)[1]=(0)(0)[1]
(0)(1)[2]=(0)(0)(0)(0)(0)[4]
(0)(1)[3]=(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)[9]

The number of copies must be a perfect square, but we want other numbers of copies for fundamental sequence. But why can't? You can imagine it easily.

(0)[0]
(0)(0)[1]
(0)(0)(0)[2]
(0)(0)(0)(0)[3]
(0)(0)(0)(0)(0)[4]
(0)(0)(0)(0)(0)(0)[5]
and so on.

I think you understand by looking at these zeroes. Now, let's analyze what matrix is what ordinal.

Now, let's analyze below.

one row (one number in each bracket)

$(0)=1$ //zero is successor.

$(0)(0)=2$ //one plus one is two.

$(0)(0)(0)=3$ //so obvious.

$(0)(1)=\omega$ //because (1) copies (0) n times. or n^2.

$(0)(1)(0)=\omega+1$ //successor again.

$(0)(1)(0)(0)=\omega+2$ //do you need this?

$(0)(1)(0)(1)=\omega2$ //two omegas are w2. what a simple!

$(0)(1)(0)(1)(0)(1)=\omega3$ //three omegas. or do you want to copy it actually?

$(0)(1)(1)=\omega^2$ //the last (1) copies (0)(1) before it

$(0)(1)(1)(0)(1)(1)=\omega^2 2$ //two w^2 are what? w^2*2.

$(0)(1)(1)(1)=\omega^3$ //adding (1) to the last makes the whole thing omega times bigger, because it copies EVERYTHING before it.

$(0)(1)(2)=\omega^{\omega}$ //so, copying (1) will be w^w.

$(0)(1)(2)(1)=\omega^{\omega+1}$ //if you don't understand this, stop googology.

$(0)(1)(2)(1)(2)=\omega^{\omega 2}$ //so, copying (1) will be w^w, but not addition this time.

$(0)(1)(2)(2)=\omega^{\omega^2}$ //last (2) copies (1)(2)

$(0)(1)(2)(2)(1)(2)=\omega^{\omega^2+\omega}$ //(1) means multiplication.

$(0)(1)(2)(2)(1)(2)(2)=\omega^{\omega^2 2}$ //so is this.

$(0)(1)(2)(2)(2)=\omega^{\omega^3}$ //I guess adding (2) is a successor to the third floor...

$(0)(1)(2)(3)=\omega^{\omega^{\omega}}$ //then, it will be like this.

$(0)(1)(2)(3)(2)(3)=\omega^{\omega^{\omega2}}$ //so is this.

$(0)(1)(2)(3)(3)=\omega^{\omega^{\omega^2}}$ //quite boring.

$(0)(1)(2)(3)(4)=\omega^{\omega^{\omega^{\omega}}}$ //obvious, right?

$(0)(1)(2)(3)(4)(5)\cdots=\epsilon_0$ //INFINITY IS FUN LOLOLOL

two rows (two numbers in each bracket)

$(0,0)(1,0)(2,0)\cdots=\epsilon_0$ //zeroes in the second row is ignored

$(0,0)(1,1)=\epsilon_0$ //because it has delta=(1,0), so fundamental sequence will be {(0,0),(0,0)(1,0),(0,0)(1,0)(2,0)...}

$(0,0)(1,1)(1,0)=\epsilon_0\times\omega$ //(1) is omega, again.

$(0,0)(1,1)(1,0)(1,0)=\epsilon_0\times\omega^2$ //so is this.

$(0,0)(1,1)(1,0)(2,0)=\epsilon_0\times\omega^{\omega}$ //are we doing the same thing again?

$(0,0)(1,1)(1,0)(2,1)=\epsilon_0\times\epsilon_0=\epsilon_0^2$ //yes, we are.

$(0,0)(1,1)(1,0)(2,1)(1,0)=\epsilon_0^2\times\omega$ //it's boring, yeah.

$(0,0)(1,1)(1,0)(2,1)(2,0)=\epsilon_0^{\omega}$ //it copies (1,0)(2,1)

$(0,0)(1,1)(1,0)(2,1)(2,0)(1,0)(2,1)=\epsilon_0^{\omega+1}$ //now, (1,0)(2,1) is e_0.

$(0,0)(1,1)(1,0)(2,1)(2,0)(1,0)(2,1)(2,0)=\epsilon_0^{\omega2}$ //there are omega of them.

$(0,0)(1,1)(1,0)(2,1)(2,0)(2,0)=\epsilon_0^{\omega^{2}}$ //there are omega of them.

$(0,0)(1,1)(1,0)(2,1)(2,0)(2,0)(2,0)=\epsilon_0^{\omega^{3}}$ //so is this.

$(0,0)(1,1)(1,0)(2,1)(2,0)(3,0)=\epsilon_0^{\omega^{\omega}}$ //obvious.

$(0,0)(1,1)(1,0)(2,1)(2,0)(3,1)=\epsilon_0^{\epsilon_0}$ //(3,1) has delta!

$(0,0)(1,1)(1,0)(2,1)(2,0)(3,1)(3,0)(4,1)=\epsilon_0^{\epsilon_0^2}$ //delta is strong!

$(0,0)(1,1)(1,1)=\epsilon_1$ //still here. (1,1) copies (0,0)(1,1), adding delta of (1,0).

$(0,0)(1,1)(1,1)(1,1)=\epsilon_2$ //the same thing happens when (1,1) is added.

$(0,0)(1,1)(2,0)=\epsilon_{\omega}$ //just repeat.

$(0,0)(1,1)(2,0)(1,1)=\epsilon_{\omega+1}$ //still the same.

$(0,0)(1,1)(2,0)(1,1)(2,0)=\epsilon_{\omega2}$ //two omegas.

$(0,0)(1,1)(2,0)(2,0)=\epsilon_{\omega^2}$ //repeats (1,1)(2,0).

$(0,0)(1,1)(2,0)(2,0)(2,0)=\epsilon_{\omega^3}$ //therefore, (2,0) is multiplication.

$(0,0)(1,1)(2,0)(3,0)=\epsilon_{\omega^{\omega}}$ //(3,0) is an omega in the second floor.

$(0,0)(1,1)(2,0)(3,1)=\epsilon_{\epsilon_0}$ //delta makes epsilon.

$(0,0)(1,1)(2,0)(3,1)(4,0)(5,1)=\epsilon_{\epsilon_{\epsilon_0}}$ //so does this.

$(0,0)(1,1)(2,1)=\zeta_0$ //delta is (2,0)

Here comes BM2!

The calculation consists of three steps.

Step One

Change n into f(n). That's all for Step One.

Step Two-A

Sep two is the main calculation step and it consists of two parts. Find the good and bad part, and then calculate $\Delta$ And, I will say as if the sequence were an matrix. To convert a sequence into a matrix is easy: write numbers in each element from up to down, and concatinate them from left to right.

• Rula 1. If the last element (P in BM1) starts with a zero, there is no bad part. That's all.

• Rule 2(else). In this tutorial, delta is considered as the number defined for each row. Execute this program. (I haven't analyzed it yet)

  Before starting, you have some preparetion: Look at the rightmost column and find the uppermost zero. mark all the numbers within the row from one above the zero to the bottom row. If there is no zero in the rightmost column, only mark the lowermost row.

  Look from right to left, but up to down in the element.

  (For example, if the sequence is (0,1)(2,3)[4], you will be look them in the order of 2,3,0,1.)

  First, if the difference between the number you're looking at and the rightmost number in that row is bigger then the delta for that row, have "to update delta." (Do not update delta at this moment - What you have is just an English-looking string.)

  If you have "to update delta", check if the number is marked.

  If the number you're looking at is marked,set the variable "bad" as the number of columns to the right of the column.

  Else, update delta for that row to the difference between the number and the the rightmost number in that row.

  Whether you see a zero or not, release the "to update delta".

  If you don't have "to update delta",

  Move on to the first row of the next(left) column.

  If you didn't use the variable "bad", set it to zero.

(I know this is some kind of "maximum difference," but I'm not sure.)

Examples:

(0,0,0)(1,1,2)(2,2,0)

0 1 2
0 1 2
0 2 0

Before calculation, you need to mark some numbers. Where is the uppermost zero in the rightmost column? It's on the third row. So you mark the numbers in the middle and bottom row.
First, look at the right-up 2. Then compare that 2 and the number in the rightmost in that row - of course that 2 again. So you don't have "to update delta" this time. Now Let's move on to the left column.
Now you are looking at 1 in the middle-up. Compare that 1 with the number in the rightmost in that row - the 2 in the right-up. 1 is smaller than 2, so you have "to update delta". Check if the number is marked. It's not marked, so change deltafor the first row to the difference between 1 and 2, namely 1.
Now you've done with the middle-up one. Where will you see next? The center one, because there was no command "move on to the next column" this time. Anyway, start dealing with the center 1. You compare 1 with 2 in the rightmost, and 1 is smaller, so you have "to update delta". The number is marked this time, so the calculation halts, leaving the variable "bad" as 1 because there is 1 column in the right of it.
And what's left? Delta is now 1,0,0 from up to down (note that you didn't change the delta for the second row), and the "bad" is 1.

(0,0,0)(1,1,0)(2,2,0)(3,3,3)

0 1 2 3
0 1 2 3
0 0 0 3

This time there is no zero in the rightmost column, so only the bottom numbers are marked.
Start from the right-up 3. Compare it with 3. 3 is not smaller than 3, so you don't have "to update delta". Move on to the next row.
Now you're looking at 2 in the first row. It's smaller than 3, so you have "to update delta". Since this number is not marked, you actually update delta, and delta for the first row becomes 1.
Then you're looking at 2 in the second row. You have "to update delta" again, and it's not marked, so delta for the second row becomes 2.
Then you're looking at 0 in the third row. You have "to update delta" again, but this time it is marked. So, the calculation halts and "bad" becomes 1.
At the end, delta becomes 1,1,0 from up and "bad" is 1. 

Step Two-B

In this step, we will calculate $C$. C is the new variable (for matrix) for BM2.

• Calculate C matrix by this program:

       for (k=1; k<=bad; k++) {
          /* Find the largest l which satisfies S_(n-bad+l)[0] < S_(n-bad+k)[0] */
          for (l=k; l>=0; l--) {
           	if (S[(n-bad+l)*nr] < S[(n-bad+k)*nr]) {
               	for (m=0; m<=row; m++) {
                   	C[m+(k+1)*nr] = ( S[m+(n-bad)*nr] < S[m+(n-bad+k)*nr] && C[m+(l+1)*nr] == 1 )? 1: 0;
               	}
                l=0;
           	}
           }
       }

Step three

     m = 1;
     while (n < nn) {
       for (l=0; l<=row; l++) {
         S[l + n*nr] = S[l + (n-bad)*nr] + Delta[l] * C[l + m*nr];
       }
       m++; n++;
       if (m > bad) m=1;
     }