Pair sequence system

A program which is supposed to calculate \(f_{\vartheta(\Omega_\omega)+1}(10)\) was posted at googology thread of Japanese BBS 2ch.net (anonymous author; now GWiki accout BashicuHyudora was created.). It is extention of a program written by the same author. The algorithm is called pair sequence system and the output of this program is called pair sequence number.

Pair sequence is a finite sequence of pair of nonnegative integers, such as (0,0)(1,1)(2,2)(3,3)(3,2). Pair sequence P works as a function from natural numbers to natural numbers, and it can be denoted as P[n], such as (0,0)(1,1)(2,2)(3,3)(3,2)[n]. The function P[n] can be approximated with Hardy hierarchy, and the pair sequence itself represents the ordinal of the approximated Hardy hierarchy, such as \((0,0)(1,1)(2,2)(3,3)(3,2) = \psi(\psi_1(\Omega_2))\).

Original BASIC Code

dim A(Infinity):dim B(Infinity):C=9
for D=0 to 9
  for E=0 to C
    A(E)=E:B(E)=E
  next
  for F=C to 0 step -1
    C=C*C
    if B(F)=0 then G=1 else G=0
    for H=0 to F*G
      if A(F-H)<A(F) or A(F)=0 then I=H:H=F*G
    next
    for J=1 to C*G*I
      A(F)=A(F-I):B(F)=B(F-I):F=F+1
    next
    G=1-G
    for K=1 to F*G
      if A(F-K)<A(F) and B(F-K)<B(F) then L=A(F)-A(F-K):M=K:K=F*G
    next
    for N=1 to C*G*M
      A(F)=A(F-M)+L:B(F)=B(F-M):F=F+1
    next
  next
next
print C

Equivalent C code

#include <stdio.h>
#include <limits.h>

/* Pair sequence number is returned from main().
   This is illustrative code and not valid. Infite array is not
   allowed in C and should be implemented with malloc()/realloc(). */ 

int main(void) {
  int a[Infinity], b[Infinity]; /* It is not allowed in C. */
  int c = 9, d, f, h, i, k;
  for (d = 0; d <= 9; d++) {
    for (h = 0; h <= c; h++) {
        a[h] = h;
        b[h] = h;
    }
    for (f = c; f >= 0; f--) {
        c = c * c;
        if (!b[f]) {
            for (h = 0; h <= f; h++) {
                if (a[f-h] < a[f] || !a[f]) {
                    k = 0;
                    i = h;
                    h = f;
                }
            }
        } else {
            for (h = 1; h <= f; h++) {
                if (a[f-h] < a[f] && b[f-h] < b[f]) {
                    k = a[f]-a[f-h];
                    i = h;
                    h = f;
                }
            }
        }
        for (h = c * i; h; h--) {
            a[f] = a[f-i] + k;
            b[f] = b[f-i];
            f++;
        }
    }
  }
  return c;
}

C code for Bignum Bakeoff rule. It has 279 characters without whitespaces.

#define A a[f]
#define B b[f]
#define F for (
#define M = malloc(9),

main(f) {
   int *a M *b M c = 9, d = 9, h, i, k;
   F ; d--;) {
      F h = c; h--;) a[h] = b[h] = h;
      F f = c; f--;) {
         c *= c;
         F h = f; h--;)
            (a[h] < A && (b[h] < B || !B) || A + B == 0)?
            (k = B ? A - a[h]: 0, i = f - h, h = 0): 0;
         h = f + c * i; a = realloc(a, h); b = realloc(b, h);
         F ; f < h; f++) A = a[f-i] + k, B = b[f-i];
      }
   }
   return c;
}

Calculation up to \(\epsilon_1\)

This program uses two arrays A and B which store pair sequence as follows. \[(A(0),B(0))(A(1),B(0))(A(2),B(2))...(A(F),B(F)) = \alpha\] where \(\alpha\) is the corresponding ordinal.

In the F loop, first B(F) is checked

    if B(F)=0 then G=1 else G=0

and when B(F)=0, only the first part is conducted. Substituting G=1,

    for H=0 to F
      if A(F-H)<A(F) or A(F)=0 then I=H:H=F
    next
    for J=1 to C*I
      A(F)=A(F-I):B(F)=B(F-I):F=F+1
    next

This is similar to the program of \(\epsilon_0\) and therefore

\begin{eqnarray*} (0,0) &=& 1 \\ (0,0)(1,0) &=& \omega \\ (0,0)(1,0)(2,0) &=& \omega^\omega \\ (0,0)(1,0)(2,0)(3,0) &=& \omega^{\omega^\omega} \\ (0,0)(1,0)(2,0)(3,0)(4,0) &=& \omega^{\omega^{\omega^\omega}} \\ \end{eqnarray*}

When B(F)>0, only the latter part is conducted with G=1. Substituting G=1,

    for K=1 to F
      if A(F-K)<A(F) and B(F-K)<B(F) then L=A(F)-A(F-K):M=K:K=F
    next
    for N=1 to C*M
      A(F)=A(F-M)+L:B(F)=B(F-M):F=F+1
    next

See how it works for (0,0)(1,1) and C=3. F=1 and at K loop, it looks for A(F-K)<A(F) and B(F-K)<B(F); it is at K=1. Therefore L=A(1)-A(0)=1, M=1. At N loop, C*M=3*1=3 pairs of (0,0) are copied, but in this copy, A is increased with L=1, so that it becomes (1,0)(2,0)(3,0). As a result, it becomes \((0,0)(1,0)(2,0)(3,0) = \omega^{\omega^\omega}\). Therefore,

\[(0,0)(1,1) = \epsilon_0\]

(n,0)(n+1,1) works in the same way and therefore

\begin{eqnarray*} (0,0)(1,1)(1,0)(2,1) &=& \epsilon_0^2 \\ (0,0)(1,1)(1,0)(2,1)(2,0)(3,1) &=& \epsilon_0^{\epsilon_0} \\ (0,0)(1,1)(1,0)(2,1)(2,0)(3,1)(3,0)(4,1) &=& \epsilon_0^{\epsilon_0^2} \\ (0,0)(1,1)(1,0)(2,1)(2,0)(3,1)(3,0)(4,1)(4,0)(5,1) &=& \epsilon_0^{\epsilon_0^{\epsilon_0}} \\ \end{eqnarray*}

See how it works for (0,0)(1,1)(1,1) and C=3. F=1 and at K loop, it looks for A(F-K)<A(F) and B(F-K)<B(F); it is at K=2. Therefore L=A(2)-A(0)=1, M=2. At N loop, C*M=3*2=6 pairs of (0,0)(1,1) are copied, but in this copy, A is increased with L=1, so that it becomes (1,0)(2,1)(2,0)(3,1)(3,0)(3,1). As a result, it becomes \((0,0)(1,1)(1,0)(2,1)(2,0)(3,1)(3,0)(4,1) = \epsilon_0^{\epsilon_0^2}\). Therefore,

\[(0,0)(1,1)(1,1) = \epsilon_1\]

Calculation up to Bachman-Howard ordinal

From here, ordinal collapsing function \(\psi\) is used as shown here.

\begin{eqnarray*} \epsilon_0 &=& \psi(0) \\ \epsilon_n &=& \psi(n) \\ \zeta_0 &=& \phi_2(0) = \psi(\Omega) \\ \phi_2(n) &=& \psi(\Omega \cdot n) \\ \phi_3(0) &=& \psi(\Omega^2) \\ \phi_\omega(0) &=& \psi(\Omega^\omega) \\ \Gamma_0 &=& \psi(\Omega^\Omega) \\ \psi(\epsilon_{\Omega+1}) &=& \psi(\psi_1(0)) \\ \psi(\zeta_{\Omega+1}) &=& \psi(\psi_1(\Omega_2)) = \psi(\Omega_2) \\ \end{eqnarray*}

The author of the program demonstrated calculation of \((0,0)(1,1)(2,2) = \psi(\psi_1(0))\) (Bachman-Howard ordinal) with constant C=1, using this simplified program.

dim A(Infinity):dim B(Infinity):C=1
for E=0 to 2
  A(E)=E:B(E)=E
next
for F=2 to 0 step -1
  if B(F)=0 then G=1 else G=0
  for H=0 to F*G
    if A(F-H)<A(F) or A(F)=0 then I=H:H=F*G
  next
  for J=1 to C*G*I
    A(F)=A(F-I):B(F)=B(F-I):F=F+1
  next
  G=1-G
  for K=1 to F*G
    if A(F-K)<A(F) and B(F-K)<B(F) then L=A(F)-A(F-K):M=K:K=F*G
  next
  for N=1 to C*G*M
    A(F)=A(F-M)+L:B(F)=B(F-M):F=F+1
  next
next
print C

According to the author of the program, at each loop, the sequence of the pairs changes and the corresponding ordinal decreases as follows. It appears to be reasonable, but I am not yet confident with the calculation. I would like to know if googologists here think this calculation is valid.

\begin{eqnarray*} (0,0)(1,1)(2,2) &=& \psi(\psi_1(0)) \\ (0,0)(1,1)(2,1) &=& \psi(\Omega) \\ (0,0)(1,1)(2,0)(3,1) &=& \psi(\psi(0)) \\ (0,0)(1,1)(2,0)(3,0) &=& \psi(\omega^\omega) \\ (0,0)(1,1)(2,0)(2,0) &=& \psi(\omega^2) \\ (0,0)(1,1)(2,0)(1,1)(2,0) &=& \psi(\omega \cdot 2) \\ (0,0)(1,1)(2,0)(1,1)(1,1) &=& \psi(\omega+2) \\ (0,0)(1,1)(2,0)(1,1)(1,0)(2,1)(3,0)(2,1) &=& \psi(\omega+1) \cdot \psi(\omega+1) \\ (0,0)(1,1)(2,0)(1,1)(1,0)(2,1)(3,0)(2,0)(3,1)(4,0) &=& \psi(\omega+1) \cdot \psi(\omega) \cdot \psi(\omega) \\ (0,0)(1,1)(2,0)(1,1)(1,0)(2,1)(3,0)(2,0)(3,1)(3,1) &=& \psi(\omega+1) \cdot \psi(\omega) \cdot \psi(1) \\ (0,0)(1,1)(2,0)(1,1)(1,0)(2,1)(3,0)(2,0)(3,1)(3,0)(4,1) &=& \psi(\omega+1) \cdot \psi(\omega) \cdot \psi(0) \cdot \psi(0) \\ (0,0)(1,1)(2,0)(1,1)(1,0)(2,1)(3,0)(2,0)(3,1)(3,0)(4,0) &=& \psi(\omega+1) \cdot \psi(\omega) \cdot \psi(0) \cdot \omega^\omega \\ (0,0)(1,1)(2,0)(1,1)(1,0)(2,1)(3,0)(2,0)(3,1)(3,0)(3,0) &=& \psi(\omega+1) \cdot \psi(\omega) \cdot \psi(0) \cdot \omega^2 \\ (0,0)(1,1)(2,0)(1,1)(1,0)(2,1)(3,0)(2,0)(3,1)(3,0)(2,0)(3,1)(3,0) &=& \psi(\omega+1) \cdot \psi(\omega) \cdot \psi(0) \cdot \omega \cdot 2 \\ (0,0)(1,1)(2,0)(1,1)(1,0)(2,1)(3,0)(2,0)(3,1)(3,0)(2,0)(3,1)(2,0)(3,1) &=& \psi(\omega+1) \cdot \psi(\omega) \cdot (\psi(0) \cdot \omega+\psi(0) \cdot 2) \\ \end{eqnarray*}

Calculation with the simplified program which was changed to C=2 was written by the author as follows. The sequence and the corresponding ordinal decrease with each loop of F as follows. This result is also shown at the verification code section.

\begin{eqnarray*} (0,0)(1,1)(2,2) &=& \psi(\psi_1(0)) \\ (0,0)(1,1)(2,1)(3,1) &=& \psi(\Omega^\Omega) \\ (0,0)(1,1)(2,1)(3,0)(4,1)(5,1)(6,0)(7,1)(8,1) &=& \psi(\Omega^{\psi(\Omega^{\psi(\Omega)})}) \\ (0,0)(1,1)(2,1)(3,0)(4,1)(5,1)(6,0)(7,1)(8,0)(9,1)(10,0)(11,1) &=& \psi(\Omega^{\psi(\Omega^{\psi(\psi(\psi(0)))})}) \\ \text{Denoting } (0,0)(1,1)(2,1)(3,0)(4,1)(5,1)(6,0)(7,1)(8,0)(9,1) &=& X \\ X(10,0)(11,0)(12,0) &=& \psi(\Omega^{\psi(\Omega^{\psi(\psi(\omega^{\omega^\omega}))})}) \\ X(10,0)(11,0)(11,0)(11,0) &=& \psi(\Omega^{\psi(\Omega^{\psi(\psi(\omega^{\omega^3}))})}) \\ X(10,0)(11,0)(11,0)(10,0)(11,0)(11,0)(10,0)(11,0)(11,0) &=& \psi(\Omega^{\psi(\Omega^{\psi(\psi(\omega^{\omega^2 \cdot 3}))})}) \\ X(10,0)(11,0)(11,0)(10,0)(11,0)(11,0)(10,0)(11,0)(10,0)(11,0)(10,0)(11,0) &=& \psi(\Omega^{\psi(\Omega^{\psi(\psi(\omega^{\omega^2 \cdot 3+\omega \cdot 3}))})}) \\ X(10,0)(11,0)(11,0)(10,0)(11,0)(11,0)(10,0)(11,0)(10,0)(11,0)(10,0)(10,0)(10,0) &=& \psi(\Omega^{\psi(\Omega^{\psi(\psi(\omega^{\omega^2 \cdot 3+\omega \cdot 2+3}))})}) \\ \end{eqnarray*}

Calculation beyond Bachman-Howard ordinal

The author wrote following result.

\begin{eqnarray*} (0,0)(1,1)(2,2)(0,0) &=& \psi(\psi_1(0))+1 \\ (0,0)(1,1)(2,2)(1,0) &=& \psi(\psi_1(0)) \omega \\ (0,0)(1,1)(2,2)(2,0) &=& \psi(\psi_1(0) \omega) \\ (0,0)(1,1)(2,2)(3,0) &=& \psi(\psi_1(\omega)) \\ (0,0)(1,1)(2,2)(3,0)(4,0) &=& \psi(\psi_1(\omega^\omega)) \\ (0,0)(1,1)(2,2)(3,0)(4,1) &=& \psi(\psi_1(\psi(0)))=\psi(\psi_1(\epsilon_0)) \\ (0,0)(1,1)(2,2)(3,1) &=& \psi(\psi_1(\Omega)) \\ (0,0)(1,1)(2,2)(3,2) &=& \psi(\psi_1(\Omega_2)) \\ (0,0)(1,1)(2,2)(3,3) &=& \psi(\psi_1(\psi_2(0))) \\ (0,0)(1,1)(2,2)(3,3)(4,4) &=& \psi(\psi_1(\psi_2(\psi_3(0)))) \\ (0,0)(1,1)(2,2)(3,3)...(9,9) &=& \psi(\psi_1(\psi_2(\psi_3(\psi_4(\psi_5(\psi_6(\psi_7(\psi_8(0))))))))) \\ \end{eqnarray*}

Therefore, in the loop of "for D=0 to 9" to "next", \(C=f_{\vartheta(\Omega_\omega)}(C)\) is calculated. Repetition of this loop 10 times results in \(f_{\vartheta(\Omega_\omega)+1}(10)\).

Verification code of C

Verification of C (.txt extention) shows calculation process. It is modified from original algorithm as follows.

• D loop eliminated
• C is set as constant 2 and does not change
• Calculation stops when the length of the sequence exceeds maxlength

The result is as follows.

• (0,0)(1,1)
• (0,0)(1,1)(1,1)
• (0,0)(1,1)(2,0)
• (0,0)(1,1)(2,1)
• (0,0)(1,1)(2,2)
• (0,0)(1,1)(2,2)(3,3)
• (0,0)(1,1)(2,2)(3,3)(4,4)