巨大数研究 Wiki
登録
Advertisement
PSS tree

ラベル付きヒドラ表現によるペア数列

ペア数列数(pair sequence number) は、バシク[1]が2014年に考案して2018年にアップデートした巨大数であり、 \(f_{\vartheta(\Omega_\omega)+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(\Omega_3+\psi_2(\Omega_3+\Omega_2))\) のように表記する。

ペア数列システムを拡張したバシク行列システムについて、現在検証がされている。ペア数列はプログラムによって定義されたが、バシク行列システムの2行行列によっても、同様に定義される。

BASIC プログラム[]

for D=0 to 9 から next のループ内で \(C=f_{\psi_0(\Omega_\omega)}(C)\) が計算され、この計算を 10 回繰り返すことで、ペア数列数 \(f_{\psi_0(\Omega_\omega)+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)[4] = (0,0)(1,1)(0,0)(1,1)(0,0)(1,1)(0,0)(1,1)(0,0)(1,1)[4]\] となり、次のような基本列が得られる。 \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 \\ \end{array} したがって、 \[(0,0)(1,1)(1,0) = \epsilon_0 \cdot \omega\] となる。次に、(0,0)(1,1)(1,0)(1,0) について考えると、 \[(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]\] となり、次のような基本列が得られる。 \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 \\ \end{array} このことから、 \[(0,0)(1,1)(1,0)(1,0) = \epsilon_0 \cdot \omega^2 \] となる。このように、数列の末尾に(1,0)を加える事で、順序数は\(\omega\)倍される。次に、数列の末尾に(1,0)(2,0)を加えることを考える。 \[(0,0)(1,1)(1,0)(2,0)[4] = (0,0)(1,1)(1,0)(1,0)(1,0)(1,0)(1,0)[4]\] のように、(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)[4] = (0,0)(1,1)(1,0)(2,1)(2,0)(3,1)(3,0)(4,1)(4,0)(5,1)[4]\] となり、次のような基本列が得られる。 \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(\omega) \\ (0,0)(1,1)(2,0)(2,0) &=& \epsilon_{\omega^2} = \psi(\omega^2) \\ (0,0)(1,1)(2,0)(3,0) &=& \epsilon_{\omega^\omega} = \psi(\omega^\omega) \\ (0,0)(1,1)(2,0)(3,1) &=& \epsilon_{\epsilon_0} = \psi(\psi(0)) \\ (0,0)(1,1)(2,0)(3,1)(4,0)(5,1) &=& \epsilon_{\epsilon_{\epsilon_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{array}

大ヴェブレン順序数 = \(\psi(\Omega^{\Omega^\Omega})\) まで[]

同様に計算を進めると、次のようになる。 \begin{array}{ll} (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{(小ヴェブレン順序数)} \\ (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{(大ヴェブレン順序数)} \end{array}

バッハマン・ハワード順序数 \(\psi(\epsilon_{\Omega+1})\) まで[]

\begin{array}{ll} (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(\epsilon_{\Omega+1}) = \psi(\psi_1(0)) \\ \end{array}

\(\psi(\Omega_\omega)\) まで[]

\begin{array}{ll} (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{array}

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

停止性の証明[]

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

出典[]

関連リンク[]

関連項目[]

Aeton: おこじょ数N成長階層
mrna: 段階配列表記降下段階配列表記多変数段階配列表記横ネスト段階配列表記
Kanrokoti: くまくまψ関数亜原始ψ関数ハイパー原始ψ関数TSS-ψ関数
クロちゃん: クロちゃん数第一第ニ第三第四
じぇいそん: ふにゃふにゃぜぇたかんすう\(\zeta\)関数
たろう: 多変数アッカーマン関数2重リストアッカーマン関数多重リストアッカーマン関数
Nayuta Ito: フラン数第一形態第二形態第四形態改三)・N原始東方巨大数4の規則の境界を突いた巨大数
バシク: 原始数列数大数列数ペア数列数バシク行列システム
長谷川由紀路: 紅魔館のメイドナンバー恋符マスタースパーク数みくみく順序数
108Hassium: E2:B-01-HsL-階差数列類E3:B-02-Hs
公太郎: 弱亜ペア数列肉ヒドラ数列弱ハイパーペア数列
p進大好きbot: 超限急増加関数表記拡張ブーフホルツのψ関数に伴う順序数表記四関数三関数巨大数庭園数
ふぃっしゅ: ふぃっしゅ数バージョン1バージョン2バージョン3バージョン4バージョン5バージョン6バージョン7)・ マシモ関数マシモスケールTR関数I0関数
ゆきと: 亜原始数列ハイパー原始数列Y数列
本: 巨大数論寿司虚空編
大会: 東方巨大数幻想巨大数即席巨大数式神巨大数お料理巨大数
掲示板: 巨大数探索スレッド名もなき巨大数研究
外部リンク: 日本語の巨大数関連サイト

Advertisement