Pair sequence number

View full site to see MathJax equation

Pair sequence number is the output of a program made by BashicuHyudora and posted at a googology-related thread of the Japanese site BBS 2ch.net in 2014.^[1]^[2]^[3]^[4], 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)\).^[5]

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.^[6] 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 calculator^[7] 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.

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

↑ First version of BASIC program
↑ Modified version of BASIC program
↑ Name of the system and the number
↑ Blog post which introduces pair sequence system
↑ BASIC program of \(\varepsilon_0\) level and a blog post which introduces it
↑ p進大好きbot, ペア数列の停止性, Japanese Googology Wiki user blog.
↑ Bashicu matrix calculator

See also[]

Googology in Japan

Original numbers, functions, notations, and notions

By Aeton: Okojo numbers · N-growing hierarchy
By 新井 (Arai): Arai's psi function
By aster: White-aster notation · White-aster
By バシク (BashicuHyudora): Primitive sequence number · Pair sequence number · Bashicu matrix system 1/2/3/4 original idea
By ふぃっしゅ (Fish): Fish numbers (Fish number 1 · Fish number 2 · Fish number 3 · Fish number 4 · Fish number 5 · Fish number 6 · Fish number 7 · S map · SS map · s(n) map · m(n) map · m(m,n) map) · Bashicu matrix system 1/2/3/4 formalisation · TR function (I0 function)
By Gaoji: Weak Buchholz's function
By じぇいそん (Jason): Irrational arrow notation · δOCF · δφ · ε function
By 甘露東風 (Kanrokoti): KumaKuma ψ function
By koteitan: Bashicu matrix system 2.3
By mrna: 段階配列表記 · 降下段階配列表記 · 多変数段階配列表記 · SSAN · S-σ
By Naruyoko Naruyo: Y sequence formalisation · ω-Y sequence formalisation
By Nayuta Ito: N primitive · Flan numbers (Flan number 1 · Flan number 2 · Flan number 3 · Flan number 4 version 3 · Flan number 5 version 3) · Large Number Lying on the Boundary of the Rule of Touhou Large Number 4 · Googology Wiki can have an article with any gibberish if it's assigned to a number
By Okkuu: Extended Weak Buchholz's function
By p進大好きbot: Ordinal notation associated to Extended Weak Buchholz's function · Ordinal notation associated to Extended Buchholz's function · Naruyoko is the great · Large Number Garden Number
By たろう (Taro): Taro's multivariable Ackermann function
By ゆきと (Yukito): Hyper primitive sequence system · Y sequence original idea · YY sequence · Y function · ω-Y sequence original idea

Methodology

By バシク (BashicuHyudora): Bashicu matrix system as a notation template
By じぇいそん (Jason): Shifting definition
By mrna: Side nesting
By Nayuta Ito and ゆきと (Yukito): Difference sequence system

Implementation of existing works into programs

By ふぃっしゅ (Fish): Ackermann function
By koteitan: Ackermann function · Beklemishev's worms · KumaKuma ψ function
By Mitsuki1729: Ackermann function · Graham's number · Conway's Tetratri · Fish number 1 · Fish number 2 · Laver table
By みずどら: White-aster notation
By Naruyoko Naruyo: p進大好きbot's Translation map for pair sequence system and Buchholz's ordinal notation · KumaKuma ψ function · Naruyoko is the great
By 猫山にゃん太 (Nekoyama Nyanta): Flan number 4 version 3 · Fish number 5 · Laver table
By Okkuu: Fish number 1 · Fish number 2 · Fish number 3 · Fish number 5 · Fish number 6
By rpakr: p進大好きbot's ordinal notation associated to Extended Weak Buchholz's function · Standardness decision algorithm for Taranovsky's ordinal notation

Proofs, translation maps for analysis schema, and other mathematical contributions

By ふぃっしゅ (Fish): Computing last 100000 digits of mega · Approximation method for FGH using Arrow notation · Translation map for primitive sequence system and Cantor normal form
By Kihara: Proof of an estimation of TREE sequence · Proof of the incomparability of Busy Beaver function and FGH associated to Kleene's \(\mathcal{O}\)
By koteitan: Translation map for primitive sequence system and Cantor normal form
By Naruyoko Naruyo: Translation map for Extended Weak Buchholz's function and Extended Buchholz's function
By Nayuta Ito: Comparison of Steinhaus-Moser Notation and Ampersand Notation
By Okkuu: Verification of みずどら's computation program of White-aster notation
By p進大好きbot: Proof of the termination of Hyper primitive sequence system · Proof of the termination of Pair sequence number · Proof of the termination of segements of TR function in the base theory under the assumption of the \(\Sigma_1\)-soundness and the pointwise well-definedness of \(\textrm{TR}(T,n)\) for the case where \(T\) is the formalisation of the base theory

Entertainments

By 小林銅蟲 (Kobayashi Doom): Sushi Kokuu Hen
By koteitan: Dancing video of a Gijinka of Fukashigi · Dancing video of a Gijinka of 久界 · Storyteller's theotre video reading Large Number Garden Number aloud