ペア数列数

ペア数列数(pair sequence number) は、バシク^[1]が2014年に考案して2018年にアップデートした巨大数であり、急増加関数とブーフホルツのψ関数を用いて\(f_{\psi_0(\psi_{\omega}(0))+1}(10)\) と近似される^[2]^[3]^[4]^[5]。このアルゴリズムはペア数列システムと言う^[6]。このプログラムは、バシクによる原始数列数のプログラムを拡張したものである。

ペア数列は、(0,0)(1,1)(2,2)(3,3)(3,2) のような非負整数ペアの有限長数列である。ペア数列 P は、自然数 n から自然数 P[n] への関数として働き、 (0,0)(1,1)(2,2)(3,3)(3,2)[n] のように書く。関数 P[n] をハーディー階層によって増加速度を近似した時の順序数を \(\alpha\) としたとき、ペア数列 P そのものが順序数 \(\alpha\) を表すものとしたいが、この対応方法は正確には関数の近似という概念が数学的に定式化されていないことや基本列によってはハーディ階層が線形階層とならないことから破綻する。一方で再帰構造が自然に持つ整礎関係を用いることで数学的に定式化され、正当化される。詳しくは基本列#展開規則を参照。例えばブーフホルツのψ関数を用いて\((0,0)(1,1)(2,2)(3,3)(3,2) = \psi_0(\psi_3(0)+\psi_2(\psi_3(0)+\psi_2(0)))\) のように表記する。

ペア数列システムの停止性が、P進大好きbotによって証明されている^[7]。さらにペア数列システムを\(n\)行行列に拡張したバシク行列システムについて、現在検証がされている。ペア数列はプログラムによって定義されたが、バシク行列システムの2行行列によっても、同様に定義される。

BASIC プログラム[]

for D=0 to 9 から next のループ内で \(C=f_{\psi_0(\psi_{\omega}(0))}(C)\) が計算され、この計算を 10 回繰り返すことで、ペア数列数 \(f_{\psi_0(\psi_{\omega}(0))+1}(10)\) を計算している。

（新バージョン: 作者本人による2018年5月26日の更新、計算の内容がオリジナルバージョンと違う）

 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

（オリジナルバージョン： 2014年8月18日に巨大数探索スレッドに投稿されたもの）

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

等価な C のプログラム[]

このプログラムは巨大数ベイクオフ大会のルールに則って、文字数を短くすることを目的として作成された。スペースと改行コードを除いて、 278 文字である。

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

main(f) {
   int *a M *b M c = 9, d = 10, h, i, k;
   W d--) {
      f = h = c + 1;
      W h--) a[h] = b[h] = h;
      W f--) {
         c *= c;
         h = f + 1;
         W 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);
         W f < h) A = a[f-i] + k, B = b[f-i], f++;
      }
   }
   return c;
}

検証用のプログラム[]

ペア数列をより一般化したバシク行列システムを計算するためのバシク行列計算機で、ペア数列の計算過程を表示することができる。また、バシク行列計算機のサイトから、C言語とBASICのプログラムをダウンロードすることが可能である。

以下が、計算例である。ここで、オリジナルのアルゴリズムでは計算のたびに n の値を2乗しているが、ここでは、n の値を n=2 のまま変えないで計算している。

対応する順序数[]

\(\epsilon_0\) まで[]

以下、ハーディ階層で近似する。 2行目が0の時は、原始数列システムと同じになる。すなわち、

\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)(1,0) &=& \omega \cdot 2 \\ (0,0)(1,0)(1,0) &=& \omega^2 \\ (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) については、次のような基本列が得られる。(簡単のため、活性化関数は\(f(n)=n\)とする。) \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} すなわち、基本列は\(\{\omega, \omega^\omega, \omega^{\omega^\omega}, \omega^{\omega^{\omega^\omega}}, \ldots\}\) となるため、 \begin{array}{ll} (0,0)(1,1) &=& \epsilon_0 \\ \end{array} となる。

\(\epsilon_1\) まで[]

次に、(0,0)(1,1)(1,0) について考えると、 \[(0,0)(1,1)(1,0) = (0,0)(1,1)(0,0)(1,1)(0,0)(1,1)(0,0)(1,1)(0,0)(1,1)...\] という基本列が得られる。これらを近似すると、 \begin{array}{ll} (0,0)(1,1) &=& \epsilon_0 \\ (0,0)(1,1)(0,0)(1,1) &=& \epsilon_0 \cdot 2 \\ (0,0)(1,1)(0,0)(1,1)(0,0)(1,1) &=& \epsilon_0 \cdot 3 \\ (0,0)(1,1)(0,0)(1,1)(0,0)(1,1)(0,0)(1,1) &=& \epsilon_0 \cdot 4 \\ (0,0)(1,1)(0,0)(1,1)(0,0)(1,1)(0,0)(1,1)(0,0)(1,1) &=& \epsilon_0 \cdot 5 \\ (0,0)(1,1)(1,0) &=& \epsilon_0 \cdot \omega \\ \end{array} となる。次に、(0,0)(1,1)(1,0)(1,0) について考えると、 \[(0,0)(1,1)(1,0)(1,0) = (0,0)(1,1)(1,0)(0,0)(1,1)(1,0)(0,0)(1,1)(1,0)...\] という基本列が得られる。これらを近似すると、 \begin{array}{ll} (0,0)(1,1)(1,0) &=& \epsilon_0 \cdot \omega \\ (0,0)(1,1)(1,0)(0,0)(1,1)(1,0) &=& \epsilon_0 \cdot \omega \cdot 2 \\ (0,0)(1,1)(1,0)(0,0)(1,1)(1,0)(0,0)(1,1)(1,0) &=& \epsilon_0 \cdot \omega \cdot 3 \\ (0,0)(1,1)(1,0)(1,0) &=& \epsilon_0 \cdot \omega^2 \\ \end{array} となる。このように、数列の末尾に(1,0)を加える事で、順序数は\(\omega\)倍される。次に、数列の末尾に(1,0)(2,0)を加えることを考える。 \[(0,0)(1,1)(1,0)(2,0) = (0,0)(1,1)(1,0)(1,0)(1,0)(1,0)(1,0)...\] のように、(1,0)が1つずつ追加される基本列ができるため、これは順序数を\(\omega^\omega\)倍することに相当し、 \[(0,0)(1,1)(1,0)(2,0) = \epsilon_0 \cdot \omega^\omega\] となる。

次に、(0,0)(1,1)(1,1) について考えると、 \[(0,0)(1,1)(1,1) = (0,0)(1,1)(1,0)(2,1)(2,0)(3,1)(3,0)(4,1)(4,0)(5,1)...\] となり、これらを近似すると、 \begin{array}{ll} (0,0)(1,1) &=& \epsilon_0 \\ (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^{\epsilon_0}} \\ (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^{\epsilon_0}}} \\ \end{array} となる。このことから、 \[(0,0)(1,1)(1,1) = \epsilon_1 \] となる。

フェファーマン・シュッテの順序数 = \(\Gamma_0\) まで[]

同様に計算を進めると、次のようになる。以下、\(\psi\)はブーフホルツのψ関数である。 \begin{array}{ll} (0,0)(1,1)(2,0) &=& \epsilon_{\omega} = \psi_0(\psi_1(\psi_0(0))) \\ (0,0)(1,1)(2,0)(2,0) &=& \epsilon_{\omega^2} = \psi_0(\psi_1(\psi_0(0) \cdot 2)) \\ (0,0)(1,1)(2,0)(3,0) &=& \epsilon_{\omega^\omega} = \psi_0(\psi_1(\psi_0(\psi_0(0)))) \\ (0,0)(1,1)(2,0)(3,1) &=& \epsilon_{\epsilon_0} = \psi_0(\psi_1(\psi_0(\psi_1(0)))) \\ (0,0)(1,1)(2,0)(3,1)(4,0)(5,1) &=& \epsilon_{\epsilon_{\epsilon_0}} = \psi_0(\psi_1(\psi_0(\psi_1(\psi_0(\psi_1(0))))) \\ (0,0)(1,1)(2,1) &=& \zeta_0 = \varphi(2,0) = \psi_0(\psi_1(\psi_1(0))) \\ (0,0)(1,1)(2,1)(1,1) &=& \varepsilon_{\zeta_0+1} = \psi_0(\psi_1(\psi_1(0))+\psi_1(0)) \\ (0,0)(1,1)(2,1)(1,1)(2,1) &=& \zeta_1= \varphi(2,1) = \psi_0(\psi_1(\psi_1(0)) \cdot 2) \\ (0,0)(1,1)(2,1)(2,0) &=& \zeta_\omega = \varphi(2,\omega) = \psi_0(\psi_1(\psi_1(0)+\psi_0(0)))\\ (0,0)(1,1)(2,1)(2,1) &=& \eta_0= \varphi(3,0) = \psi_0(\psi_1(\psi_1(0) \cdot 2))\\ (0,0)(1,1)(2,1)(2,1)(2,1) &=& \varphi(4,0) = \psi_0(\psi_1(\psi_1(0) \cdot 3))\\ (0,0)(1,1)(2,1)(3,0) &=& \varphi(\omega,0) = \psi_0(\psi_1(\psi_1(\psi_0(0))))\\ (0,0)(1,1)(2,1)(3,1) &=& \Gamma_0 = \varphi(1,0,0) = \psi_0(\psi_1(\psi_1(\psi_1(0))))\\ \end{array}

バッハマン・ハワード順序数 \(\psi_0(\psi_2(0))\) まで[]

同様に計算を進めると、次のようになる。 \begin{array}{ll} (0,0)(1,1)(2,1)(3,1)(1,1) &=& \psi_0(\psi_1(\psi_1(\psi_1(0)))+\psi_1(0)) \\ (0,0)(1,1)(2,1)(3,1)(1,1)(2,1) &=& \psi_0(\psi_1(\psi_1(\psi_1(0)))+\psi_1(\psi_1(0))) \\ (0,0)(1,1)(2,1)(3,1)(1,1)(2,1)(3,1) &=& \psi_0(\psi_1(\psi_1(\psi_1(0))) \cdot 2) \\ (0,0)(1,1)(2,1)(3,1)(2,0) &=& \psi_0(\psi_1(\psi_1(\psi_1(0))+\psi_0(0))) \\ (0,0)(1,1)(2,1)(3,1)(2,1) &=& \psi_0(\psi_1(\psi_1(\psi_1(0))+\psi_1(0))) \\ (0,0)(1,1)(2,1)(3,1)(2,1)(3,1) &=& \psi_0(\psi_1(\psi_1(\psi_1(0)) \cdot 2)) \\ (0,0)(1,1)(2,1)(3,1)(3,0) &=& \psi_0(\psi_1(\psi_1(\psi_1(0)+\psi_0(0)))) \\ (0,0)(1,1)(2,1)(3,1)(3,1) &=& \psi_0(\psi_1(\psi_1(\psi_1(0) \cdot 2))) \\ (0,0)(1,1)(2,1)(3,1)(3,1)(3,0) &=& \psi_0(\psi_1(\psi_1(\psi_1(0) \cdot 2+\psi_0(0)))) \\ (0,0)(1,1)(2,1)(3,1)(3,1)(3,1) &=& \psi_0(\psi_1(\psi_1(\psi_1(0) \cdot 3))) \\ (0,0)(1,1)(2,1)(3,1)(3,1)(3,1)(3,1) &=& \psi_0(\psi_1(\psi_1(\psi_1(0) \cdot 4))) \\ (0,0)(1,1)(2,1)(3,1)(4,0)&=& \psi_0(\psi_1(\psi_1(\psi_1(\psi_0(0))))) \text{(小ヴェブレン順序数)} \\ (0,0)(1,1)(2,1)(3,1)(4,0)(4,0) &=& \psi_0(\psi_1(\psi_1(\psi_1(\psi_0(0) \cdot 2)))) \\ (0,0)(1,1)(2,1)(3,1)(4,0)(5,0) &=& \psi_0(\psi_1(\psi_1(\psi_1(\psi_0(\psi_0(0)))))) \\ (0,0)(1,1)(2,1)(3,1)(4,0)(5,1) &=& \psi_0(\psi_1(\psi_1(\psi_1(\psi_0(\psi_1(0)))))) \\ (0,0)(1,1)(2,1)(3,1)(4,0)(5,1)(6,1)(7,1) &=& \psi_0(\psi_1(\psi_1(\psi_1(\psi_0(\psi_1(\psi_1(\psi_1(0)))))))) \\ (0,0)(1,1)(2,1)(3,1)(4,1) &=& \psi_0(\psi_1(\psi_1(\psi_1(\psi_1(0))))) \text{(大ヴェブレン順序数)} \\ (0,0)(1,1)(2,1)(3,1)(4,1)(4,0) &=& \psi_0(\psi_1(\psi_1(\psi_1(\psi_1(0)+\psi_0(0))))) \\ (0,0)(1,1)(2,1)(3,1)(4,1)(4,1) &=& \psi_0(\psi_1(\psi_1(\psi_1(\psi_1(0) \cdot 2)))) \\ (0,0)(1,1)(2,1)(3,1)(4,1)(5,0) &=& \psi_0(\psi_1(\psi_1(\psi_1(\psi_1(\psi_0(0)))))) \\ (0,0)(1,1)(2,1)(3,1)(4,1)(5,1) &=& \psi_0(\psi_1(\psi_1(\psi_1(\psi_1(\psi_1(0)))))) \\ (0,0)(1,1)(2,1)(3,1)(4,1)(5,1)(6,1) &=& \psi_0(\psi_1(\psi_1(\psi_1(\psi_1(\psi_1(\psi_1(0))))))) \\ (0,0)(1,1)(2,2) &=& \psi_0(\psi_2(0)) \text{(バッハマン・ハワード順序数)} \\ \end{array}

\(\psi_0(\psi_{\omega}(0))\) まで[]

\begin{array}{ll} (0,0)(1,1)(2,2)(0,0) &=& \psi_0(\psi_2(0))+1 \\ (0,0)(1,1)(2,2)(1,0) &=& \psi_0(\psi_2(0)+\psi_0(0)) \\ (0,0)(1,1)(2,2)(1,1) &=& \psi_0(\psi_2(0)+\psi_1(0)) \\ (0,0)(1,1)(2,2)(1,1)(2,2) &=& \psi_0(\psi_2(0)+\psi_1(\psi_2(0))) \\ (0,0)(1,1)(2,2)(2,0) &=& \psi_0(\psi_2(0)+\psi_1(\psi_2(0)+\psi_0(0))) \\ (0,0)(1,1)(2,2)(2,1) &=& \psi_0(\psi_2(0)+\psi_1(\psi_2(0)+\psi_1(0))) \\ (0,0)(1,1)(2,2)(2,1)(3,2) &=& \psi_0(\psi_2(0)+\psi_1(\psi_2(0)+\psi_1(\psi_2(0)))) \\ (0,0)(1,1)(2,2)(2,2) &=& \psi_0(\psi_2(0) \cdot 2) \\ (0,0)(1,1)(2,2)(3,0) &=& \psi_0(\psi_2(\psi_0(0))) \\ (0,0)(1,1)(2,2)(3,0)(4,1) &=& \psi_0(\psi_2(\psi_0(\psi_1(0)))) \\ (0,0)(1,1)(2,2)(3,0)(4,1)(5,2) &=& \psi_0(\psi_2(\psi_0(\psi_2(0)))) \\ (0,0)(1,1)(2,2)(3,1) &=& \psi_0(\psi_2(\psi_1(0))) \\ (0,0)(1,1)(2,2)(3,2) &=& \psi_0(\psi_2(\psi_2(0))) \\ (0,0)(1,1)(2,2)(3,3) &=& \psi_0(\psi_3(0)) \\ (0,0)(1,1)(2,2)(3,3)(4,4) &=& \psi_0(\psi_4(0)) \\ (0,0)(1,1)(2,2)(3,3)(4,4)(5,5) &=& \psi_0(\psi_5(0)) \\ \end{array}

すなわち、\(Pair(n) = (0,0)(1,1) \ldots (n,n)[n]\) とすると、 \[Pair(n) \approx f_{\psi_0(\psi_{\omega}(0))}(n)\] となる。

停止性の証明[]

P進大好きbot は標準形という概念（通常の意味での標準形より広い）を定義し、ブーフホルツのψ関数を用いてペア数列システムの停止性を証明した。^[8]

出典[]

↑ 作者のFandomアカウント
↑ 巨大数探索スレッド10: 初版の定義
↑ 巨大数探索スレッド10: 修正版の定義
↑ 巨大数探索スレッド10: 計算
↑ 巨大数論
↑ 「ペア数列システム」と「ペア数列数」を名付けたのは巨大数探索スレッド10の186である。
↑ ユーザーブログ:P進大好きbot/ペア数列の停止性
↑ ユーザーブログ:P進大好きbot/ペア数列の停止性