Pair sequence number

Pair sequence number is the output of a program made by and posted at a googology-related thread of the Japanese site BBS 2ch.net in 2014.First version of BASIC programModified version of BASIC programName of the system and the numberBlog post which introduces pair sequence system, and updated by BashicuHyudora in 2017 on Japanese googology wiki. The algorithm of the program is called the pair sequence system, a weak version of Bashicu matrix system by the same creator. It is supposed to calculate a number comparable to \(f_{\psi_0(\Omega_\omega)+1}(10)\) with respect to Buchholz's function. It is an extension of a system named the primitive sequence system by the same author, which generates a number comparable to \(f_{\varepsilon_0+1}(10)\).BASIC program of \(\varepsilon_0\) level and a blog post which introduces it
A pair sequence is a finite sequence of pairs of nonnegative integers, for example (0,0)(1,1)(2,2)(3,3)(3,2). A pair sequence P works as a function from natural numbers to natural numbers, (though we write P[n] rather than P(n)), for example \(n \mapsto (0,0)(1,1)(2,2)(3,3)(3,2)[n]\) is a function. The function P[n] is usually approximated with a function of the form \(H_\alpha\) from the Hardy hierarchy (we note \(P = \alpha\)). For example, \((0,0)(1,1)(2,2)(3,3)(3,2)\) corresponds to \(\psi_0(\Omega_3+\psi_2(\Omega_3+\Omega_2))\) with respect to Buchholz's function.
== Termination ==
A Japanese Googology Wiki user p進大好きbot verified its termination.p進大好きbot, ペア数列の停止性, Japanese Googology Wiki user blog. See #External Links for a pdf-translation of the proof translated by koteitan and a pdf-translation of a latex-translation of the proof translated by Naruyoko.
== Original BASIC Code ==
In the following program, in the loop starting from "for D=0 to 9" and ending at "next", a number close of \(f_{\psi_0(\Omega_\omega)}(C)\) with respect to Buchholz's function is generated. The program repeats this loop 10 times and finally outputs a number close of \(f_{\psi_0(\Omega_\omega)+1}(10)\) with respect to Buchholz's function.
dim A[∞],B[∞]: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
 for G=0 to C
 if A[F]=0 | (A[F-G]<A[F] & (B[F]=0 | B[F-G]<B[F])) then H=G:G=C
 next
 if B[F]=0 then I=0 else I=A[F]-A[F-H]
 for J=1 to C*H
 A[F]=A[F-H]+I:B[F]=B[F-H]:F=F+1
 next
 next
 next
 print C
== Modified BASIC code ==
The modified version was posted on Japanese version of this page on May 26, 2018 by Bashicu, the author of this program. Bashicu mentions that the original version does not reach \(\psi_0(\Omega_\omega)\) level with respect to Buchholz's function as expected, with (0,0)(1,1)(2,2)(3,0)(2,1)(3,1)(4,1) as the counterexample, and this version will reach this level.
dim A[∞],B[∞]: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
 for G=0 to F
 if A[F]=0 | A[F-G]<A[F]-H then
 if B[F]=0 then 
 I=G:G=F
 else
 H=A[F]-A[F-G]
 if B[F-G]<B[F] then I=G:G=F
 endif
 endif
 next
 for J=1 to C*I
 A[F]=A[F-I]+H:B[F]=B[F-I]:F=F+1
 next
 H=0
 next
 next
 print C
== Verification code ==
The Bashicu matrix calculatorBashicu matrix calculator shows the calculation process of pair sequence system. BM1 corresponds to the original version.
Here are some examples of the calculation of some pair sequences. The algorithm is modified so that it always take n=2.
* (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)
== Corresponding ordinals ==
During the proof of the termination, p進大好きbot verified that each standard pair sequence \(M\) corresponds to an ordinal \(\textrm{Trans}(M)\) below \(\psi_0(\Omega_{\omega})\) so that the expansion expansion of \(M\) gives a strictly increasing sequence of ordinals below \(\textrm{Trans}(M)\). In particular, it implies that pair sequence system restricted to standard pair sequences gives a total computable function whose structural well-ordering is of ordinal type bounded by \(\psi_0(\Omega_{\omega})\). See #External Links for Naruyoko's implementation of \(\textrm{Trans}\) into Javascript.
It is also strongly believed in this community that the structural well-ordering is of ordinal type \(\psi_0(\Omega_{\omega})\).
The following are analyses of the structural well-ordering based on Bashicu's unspecified OCF which is different from Buchholz's function without a proof:
=== Up to \(\varepsilon_0\) ===
When all the values of the second row are 0, it is the same as the primitive sequence system. We have:
\begin{array}{ll}
(0,0) &=& 1 \\
(0,0)(0,0) &=& 2 \\
(0,0)(0,0)(0,0) &=& 3 \\
(0,0)(1,0) &=& \omega \\
(0,0)(1,0)(0,0) &=& \omega+1 \\
(0,0)(1,0)(0,0)(0,0) &=& \omega+2 \\
(0,0)(1,0)(0,0)(1,0) &=& \omega \cdot 2 \\
(0,0)(1,0)(1,0) &=& \omega^2 \\
(0,0)(1,0)(1,0)(0,0)(1,0) &=& \omega^2+\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{array}
(0,0)(1,1) has fundamental sequence as follows. Here, n is not changed.
\begin{array}{ll}
(0,0)(1,1)[1] &=& (0,0)(1,0)[1] \\
(0,0)(1,1)[2] &=& (0,0)(1,0)(2,0)[2] \\
(0,0)(1,1)[3] &=& (0,0)(1,0)(2,0)(3,0)[3] \\
(0,0)(1,1)[4] &=& (0,0)(1,0)(2,0)(3,0)(4,0)[4] \\
\end{array}
Therefore, \(\{\omega, \omega^\omega, \omega^{\omega^\omega}, \omega^{\omega^{\omega^\omega}}, \ldots\}\) and
\begin{array}{ll}
(0,0)(1,1) &=& \varepsilon_0 \\
\end{array}
=== Up to \(\varepsilon_1\) ===
As for (0,0)(1,1)(1,0),
\[(0,0)(1,1)(1,0)[4] = (0,0)(1,1)(0,0)(1,1)(0,0)(1,1)(0,0)(1,1)(0,0)(1,1)[4]\]
and the fundamental sequence is
\begin{array}{ll}
(0,0)(1,1) &=& \varepsilon_0 \\
(0,0)(1,1)(0,0)(1,1) &=& \varepsilon_0 \cdot 2 \\
(0,0)(1,1)(0,0)(1,1)(0,0)(1,1) &=& \varepsilon_0 \cdot 3 \\
(0,0)(1,1)(0,0)(1,1)(0,0)(1,1)(0,0)(1,1) &=& \varepsilon_0 \cdot 4 \\
(0,0)(1,1)(0,0)(1,1)(0,0)(1,1)(0,0)(1,1)(0,0)(1,1) &=& \varepsilon_0 \cdot 5 \\
\end{array}
Therefore,
\[(0,0)(1,1)(1,0) = \varepsilon_0 \cdot \omega = \omega^{\varepsilon_0+1}\]
\[(0,0)(1,1)(1,0)(1,0)[2] = (0,0)(1,1)(1,0)(0,0)(1,1)(1,0)(0,0)(1,1)(1,0)[2]\]
has fundamental sequence of
\begin{array}{ll}
(0,0)(1,1)(1,0) &=& \varepsilon_0 \cdot \omega &=& \omega^{\varepsilon_0+1} \\
(0,0)(1,1)(1,0)(0,0)(1,1)(1,0) &=& \varepsilon_0 \cdot \omega \cdot 2 &=& \omega^{\varepsilon_0+1}\cdot 2 \\
(0,0)(1,1)(1,0)(0,0)(1,1)(1,0)(0,0)(1,1)(1,0) &=& \varepsilon_0 \cdot \omega \cdot 3 &=& \omega^{\varepsilon_0+1}\cdot 3 \\
\end{array}
Therefore,
\[(0,0)(1,1)(1,0)(1,0) = \varepsilon_0 \cdot \omega^2 = \omega^{\varepsilon_0+2} \]
In this way, adding (1,0) to the end of the sequence makes the ordinal \(\omega\) times. Adding (1,0)(2,0) to the end of the sequence
\[(0,0)(1,1)(1,0)(2,0)[4] = (0,0)(1,1)(1,0)(1,0)(1,0)(1,0)(1,0)[4]\]
corresponds to multiplying \(\omega^\omega\) to the ordinal, and therefore
\[(0,0)(1,1)(1,0)(2,0) = \varepsilon_0 \cdot \omega^\omega = \omega^{\varepsilon_0+\omega}\]
As for (0,0)(1,1)(1,1),
\[(0,0)(1,1)(1,1)[4] = (0,0)(1,1)(1,0)(2,1)(2,0)(3,1)(3,0)(4,1)(4,0)(5,1)[4]\]
and the following fundamental sequence is obtained.
\begin{array}{ll}
(0,0)(1,1) &=& \varepsilon_0 \\
(0,0)(1,1)(1,0)(2,1) &=& \varepsilon_0^2 &=& \omega^{\varepsilon_0\cdot 2} \\
(0,0)(1,1)(1,0)(2,1)(2,0)(3,1) &=& \varepsilon_0^{\varepsilon_0} &=& \omega^{\omega^{\varepsilon_0\cdot 2}} \\
(0,0)(1,1)(1,0)(2,1)(2,0)(3,1)(3,0)(4,1) &=& \varepsilon_0^{\varepsilon_0^2} &=& \omega^{\omega^{\omega^{\varepsilon_0\cdot 2}}} \\
(0,0)(1,1)(1,0)(2,1)(2,0)(3,1)(3,0)(4,1)(4,0)(5,1) &=& \varepsilon_0^{\varepsilon_0^{\varepsilon_0}} &=& \omega^{\omega^{\omega^{\omega^{\varepsilon_0\cdot 2}}}} \\
\end{array}
Therefore,
\[(0,0)(1,1)(1,1) = \varepsilon_1 = \psi(1) \]
=== Up to Feferman-Schutte ordinal = \(\Gamma_0\) ===
Similar calculation results in (with respect to Madore's function):
\begin{eqnarray*}
(0,0)(1,1)(2,0) &=& \varepsilon_{\omega} &=& \psi(\omega) \\
(0,0)(1,1)(2,0)(2,0) &=& \varepsilon_{\omega^2} &=& \psi(\omega^2) \\
(0,0)(1,1)(2,0)(3,0) &=& \varepsilon_{\omega^\omega} &=& \psi(\omega^\omega) \\
(0,0)(1,1)(2,0)(3,1) &=& \varepsilon_{\varepsilon_0} &=& \psi(\psi(0)) \\
(0,0)(1,1)(2,0)(3,1)(4,0)(5,1) &=& \varepsilon_{\varepsilon_{\varepsilon_0}} &=& \psi(\psi(\psi(0))) \\
(0,0)(1,1)(2,1) &=& \zeta_0 &=& \psi(\Omega) &=& \varphi(2,0) \\
(0,0)(1,1)(2,1)(1,1) &=& \varepsilon_{\zeta_0+1} \\
(0,0)(1,1)(2,1)(1,1)(2,1) &=& \zeta_1 &=& \varphi(2,1) \\
(0,0)(1,1)(2,1)(2,0) &=& \zeta_\omega &=& \varphi(2,\omega) \\
(0,0)(1,1)(2,1)(2,1) &=& \eta_0 &=& \varphi(3,0) \\
(0,0)(1,1)(2,1)(2,1)(2,1) &=& \varphi(4,0) \\
(0,0)(1,1)(2,1)(3,0) &=& \varphi(\omega,0) \\
(0,0)(1,1)(2,1)(3,1) &=& \Gamma_0 &=& \psi(\Omega^\Omega) &=& \varphi(1,0,0) 
\end{eqnarray*}
=== Up to Large Veblen ordinal = \(\psi_0(\Omega^{\Omega^\Omega})\) with respect to Buchholz's function ===
\begin{eqnarray*}
(0,0)(1,1)(2,1)(3,1)(1,1) &=& \varepsilon_{\Gamma_0+1} \\
(0,0)(1,1)(2,1)(3,1)(1,1)(2,1) &=& \zeta_{\Gamma_0+1} \\
(0,0)(1,1)(2,1)(3,1)(1,1)(2,1)(3,1) &=& \Gamma_1 &=& \varphi(1,0,1) \\
(0,0)(1,1)(2,1)(3,1)(2,0) &=& \Gamma_\omega &=& \varphi(1,0,\omega) \\
(0,0)(1,1)(2,1)(3,1)(2,1) &=& \varphi(1,1,0) \\
(0,0)(1,1)(2,1)(3,1)(2,1)(1,1)(2,1)(3,1)(2,1) &=& \varphi(1,1,1) \\
(0,0)(1,1)(2,1)(3,1)(2,1)(2,0) &=& \varphi(1,1,\omega) \\
(0,0)(1,1)(2,1)(3,1)(2,1)(2,1) &=& \varphi(1,2,0) \\
(0,0)(1,1)(2,1)(3,1)(2,1)(3,1) &=& \varphi(2,0,0) \\
(0,0)(1,1)(2,1)(3,1)(3,0) &=& \varphi(\omega,0,0) \\
(0,0)(1,1)(2,1)(3,1)(3,1) &=& \varphi(1,0,0,0) \\
(0,0)(1,1)(2,1)(3,1)(3,1)(1,1)(2,1)(3,1)(3,1) &=& \varphi(1,0,0,1) \\
(0,0)(1,1)(2,1)(3,1)(3,1)(2,1) &=& \varphi(1,0,1,0) \\
(0,0)(1,1)(2,1)(3,1)(3,1)(2,1)(3,1) &=& \varphi(1,1,0,0) \\
(0,0)(1,1)(2,1)(3,1)(3,1)(2,1)(3,1)(2,1)(3,1) &=& \varphi(1,2,0,0) \\
(0,0)(1,1)(2,1)(3,1)(3,1)(2,1)(3,1)(3,1) &=& \varphi(2,0,0,0) \\
(0,0)(1,1)(2,1)(3,1)(3,1)(2,1)(3,1)(3,1)(2,1)(3,1)(3,1) &=& \varphi(3,0,0,0) \\
(0,0)(1,1)(2,1)(3,1)(3,1)(3,0) &=& \varphi(\omega,0,0,0) \\
(0,0)(1,1)(2,1)(3,1)(3,1)(3,1) &=& \varphi(1,0,0,0,0) &=& \psi(\Omega^{\Omega^3}) \\
(0,0)(1,1)(2,1)(3,1)(3,1)(3,1)(3,1) &=& \varphi(1,0,0,0,0,0) &=& \psi(\Omega^{\Omega^4}) \\
(0,0)(1,1)(2,1)(3,1)(4,0)&=& \psi(\Omega^{\Omega^\omega}) &&\text{(SVO)} \\
(0,0)(1,1)(2,1)(3,1)(4,0)(3,1) &=& \psi(\Omega^{\Omega^{\omega+1}}) \\
(0,0)(1,1)(2,1)(3,1)(4,0)(4,0) &=& \psi(\Omega^{\Omega^{\omega^2}}) \\
(0,0)(1,1)(2,1)(3,1)(4,0)(5,0) &=& \psi(\Omega^{\Omega^{\omega^\omega}}) \\
(0,0)(1,1)(2,1)(3,1)(4,0)(5,1) &=& \psi(\Omega^{\Omega^{\varepsilon_0}}) \\
(0,0)(1,1)(2,1)(3,1)(4,1) &=& \psi(\Omega^{\Omega^\Omega}) &&\text{(LVO)}
\end{eqnarray*}
=== Up to Bachmann-Howard ordinal ===
\begin{eqnarray*}
(0,0)(1,1)(2,1)(3,1)(4,1)(4,0) &=& \psi(\Omega^{\Omega^{\Omega \cdot \omega}}) \\
(0,0)(1,1)(2,1)(3,1)(4,1)(4,1) &=& \psi(\Omega^{\Omega^{\Omega^2}}) \\
(0,0)(1,1)(2,1)(3,1)(4,1)(5,0) &=& \psi(\Omega^{\Omega^{\Omega^\omega}}) \\
(0,0)(1,1)(2,1)(3,1)(4,1)(5,1) &=& \psi(\Omega^{\Omega^{\Omega^\Omega}}) \\
(0,0)(1,1)(2,1)(3,1)(4,1)(5,1)(6,1) &=& \psi(\Omega^{\Omega^{\Omega^{\Omega^\Omega}}}) \\
(0,0)(1,1)(2,1)(3,1)(4,1)(5,1)(6,1)(7,1) &=& \psi(\Omega^{\Omega^{\Omega^{\Omega^{\Omega^\Omega}}}}) \\
(0,0)(1,1)(2,2) &=& \psi(\varepsilon_{\Omega+1}) &=& \psi(\psi_2(0))
\end{eqnarray*}
=== Up to \(\psi_0(\Omega_\omega)\) with respect to Buchholz's function ===
\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))\cdot\omega \\
(0,0)(1,1)(2,2)(2,0) &=& \psi(\psi_1(0)\cdot\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(\varepsilon_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*}
By defining \(\textrm{Pair}(n) = (0,0)(1,1) \ldots (n,n)[n]\), one has an expectation
\[\textrm{Pair}(n) \approx f_{\psi_0(\Omega_\omega)}(n)\]
with respect to Buchholz's function and the canonical system of fundamental sequences. Be careful that the \(\psi\) in the analyses is not Buchholz's function but Bashicu's unspecified OCF.
== External Links ==
* A pdf-translation of p進大好きbot's proof of the termination of Pair Sequence System translated by koteitan. (71 pages)
* A pdf-trnslation of a latex-translation of p進大好きbot's proof of the termination of Pair Sequence System translated by Naruyoko. (142 pages)
* A short summary of the document above given by removing proofs from arguments in the latex-translation of p進大好きbot's proof of the termination of Pair Sequence System translated by Naruyoko. (47 pages)
* A computation programme of \(\textrm{Trans}\) in p進大好きbot's proof of the termination of Pair Sequence System implemented into Javascript by Naruyoko.
== Sources ==
== See also ==
ja:ペア数列数zh:對數列系統
Category:Bashicu matrix system
Category:Higher computable level
Category:Googology in Asia
Category:Numbers
Category:Numbers by Bashicu
Category:Functions