hydra notation example

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 verified to terminate by a Japanese Googology Wiki user p進大好きbot,[5] and is supposed to calculate number comparable to \(f_{\psi(\Omega_\omega)+1}(10)\) with respect to Buchholz's function. It is an extension of a system named the primitive sequence system, still by the same author, which generates a number approaching \(f_{\varepsilon_0+1}(10)\).[6]

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.

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(\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(\Omega_\omega)+1}(10)\) with respect to Buchholz's function.

 1 dim A[],B[]:C=9
 2  for D=0 to 9
 3   for E=0 to C
 4    A[E]=E:B[E]=E
 5   next
 6   for F=C to 0 step -1
 7    C=C*C
 8    for G=0 to C
 9     if A[F]=0 | (A[F-G]<A[F] & (B[F]=0 | B[F-G]<B[F])) then H=G:G=C
10    next
11    if B[F]=0 then I=0 else I=A[F]-A[F-H]
12    for J=1 to C*H
13     A[F]=A[F-H]+I:B[F]=B[F-H]:F=F+1
14    next
15   next
16  next
17  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(\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.

 1 dim A[],B[]:C=9
 2  for D=0 to 9
 3   for E=0 to C
 4    A[E]=E:B[E]=E
 5   next
 6   for F=C to 0 step -1
 7    C=C*C
 8    for G=0 to F
 9     if A[F]=0 | A[F-G]<A[F]-H  then
10      if B[F]=0 then 
11       I=G:G=F
12      else
13       H=A[F]-A[F-G]
14       if B[F-G]<B[F] then I=G:G=F
15      endif
16     endif
17    next
18    for J=1 to C*I
19     A[F]=A[F-I]+H:B[F]=B[F-I]:F=F+1
20    next
21    H=0
22   next
23  next
24  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

It is verified that each standard pair sequence \(M\) corresponds to an ordinal \(\textrm{Trans}(M)\) below \(\psi(\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 stractural well-ordering is of ordinal type bounded by \(\psi(\Omega_{\omega})\). It is also strongly believed in this community that the structural well-ordering is of ordinal type \(\psi(\Omega_{\omega})\).

The following are analyses of the structural well-ordering based on an 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)(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\]

\[(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 \\ (0,0)(1,1)(1,0)(0,0)(1,1)(1,0) &=& \varepsilon_0 \cdot \omega \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 \\ \end{array}

Therefore, \[(0,0)(1,1)(1,0)(1,0) = \varepsilon_0 \cdot \omega^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\]

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 \\ (0,0)(1,1)(1,0)(2,1)(2,0)(3,1) &=& \varepsilon_0^{\varepsilon_0} \\ (0,0)(1,1)(1,0)(2,1)(2,0)(3,1)(3,0)(4,1) &=& \varepsilon_0^{\varepsilon_0^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}} \\ \end{array} Therefore, \[(0,0)(1,1)(1,1) = \varepsilon_1 = \psi(1) \]

Up to Feferman–Schütte ordinal = \(\Gamma_0\)

Similar calculation results in:

\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 = \varphi(2,0) = \psi(\Omega) \\ (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 = \varphi(1,0,0) = \psi(\Omega^\Omega) \end{eqnarray*}

Up to Large Veblen ordinal = \(\psi(\Omega^{\Omega^\Omega})\)

\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) &=& ψ(\Omega^{\Omega^{\Omega^{\Omega^\Omega}}}) \\ (0,0)(1,1)(2,1)(3,1)(4,1)(5,1)(6,1)(7,1) &=& ψ(\Omega^{\Omega^{\Omega^{\Omega^{\Omega^\Omega}}}}) \\ (0,0)(1,1)(2,2) &=& \psi(\varepsilon_{\Omega+1}) = \psi(\psi_1(0)) \end{eqnarray*}

Up to \(\psi(\Omega_\omega)\)

\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(\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(\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.

Sources

See also

Fish numbers: Fish number 1 · Fish number 2 · Fish number 3 · Fish number 4 · Fish number 5 · Fish number 6 · Fish number 7
Mapping functions: S map · SS map · S(n) map · M(n) map · M(m,n) map
By Aeton: Okojo numbers · N-growing hierarchy
By BashicuHyudora: Primitive sequence number · Pair sequence number · Bashicu matrix system
By Kanrokoti: KumaKuma ψ function
By 巨大数大好きbot: Flan numbers
By Jason: Irrational arrow notation · δOCF · δφ · ε function
By mrna: 段階配列表記 · 降下段階配列表記 · 多変数段階配列表記 · SSAN · S-σ
By Nayuta Ito: N primitive
By p進大好きbot: Large Number Garden Number
By Yukito: Hyper primitive sequence system · Y sequence · YY sequence · Y function
Indian counting system: Lakh · Crore · Tallakshana · Uppala · Dvajagravati · Paduma · Mahakathana · Asankhyeya · Dvajagranisamani · Vahanaprajnapti · Inga · Kuruta · Sarvanikshepa · Agrasara · Uttaraparamanurajahpravesa · Avatamsaka Sutra · Nirabhilapya nirabhilapya parivarta
Chinese, Japanese and Korean counting system: Wan · Yi · Zhao · Jing · Gai · Zi · Rang · Gou · Jian · Zheng · Zai · Ji · Gougasha · Asougi · Nayuta · Fukashigi · Muryoutaisuu
Other: Taro's multivariable Ackermann function · TR function · Arai's \(\psi\) · Sushi Kokuu Hen

Community content is available under CC-BY-SA unless otherwise noted.