FANDOM

10,835 Pages

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.).[1][2] 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.[3]

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

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.

Sources

1. First version of BASIC program
2. Modified version of BASIC program
3. Name of the system and the number
4. The author's calculation (154-160, 164-169, 174-184)