原始数列数

原始数列数(primitive sequence number) は、バシク^[1]^[2]が考案した巨大数である^[3]^[4]。原始数列数を生み出すアルゴリズムを原始数列システムと言い、ベクレミシェフの虫とよく似ていて、\(f_{\varepsilon_0}(n)\) の強さを持つ。原始数列数の大きさは \(f_{\varepsilon_0+1}(10)\) 程度である。

原始数列システムを発展させたペア数列システムは、\(f_{\psi_0(\Omega_{\omega})}(n)\) の強さを持つ。さらに発展させたトリオ数列システム、バシク行列システムについて、現在検証が進められている。

定義[]

原始数列数の初めの定義は BASIC 言語の疑似コードとして２ちゃんねるの巨大数探索スレッド10 に投稿された。(本ページの右上のプログラム。) その後、定義は巨大数 Wiki のユーザーブログの BASIC言語による巨大数のまとめの記事上でメンテナンスされている。

オリジナルと同等な数学的定義[]

オリジナルの定義は BASIC 言語の疑似コードで定義されているが、それと同等の数学的な定義は下記のようになる。

原始数列とは、非負整数のリストのことである。与えられた原始数列 \(S\) と非負整数 \(n\) に対し、非負整数 \(S[n]\) を以下のように再帰的に定める。ただしここでは\(S\)を\((S_0,\ldots,S_k)\)（\(k,S_0,\ldots,S_k\)はいずれも非負整数）と表す。

\(S\)が空列\(()\)であるならば、\(S[n] = n\)である。すなわち \( ( )[n]=n \) である。
\(S\)が空列\(()\)でないならば、\(S\) の良い部分 (good part) \(g\) と悪い部分 (bad part) \(b\) を、下記のように決め、\(S[n] = (g \frown b \underbrace{\frown b \frown \cdots \frown b}_{f(n) ~\mathrm{個の}~\frown b})[f(n)]\) とする。ここで、\(f(n)\) は \(f(n)=n^2\) である。
- \(i<k\) かつ \(S_i<S_k\) をみたす最大の非負整数 \(i\) が存在するときは \(g=(S_0,\ldots,S_{i-1}),~b= (S_{i},\ldots,S_{k-1})\) とする。
- 上記の \(i\) が存在しないときは \(g=(S_0, \ldots, S_{k−1}),~b=( ) \) とする。

\(S[n]\) の定義は以上である。

ここで\(\frown\) は数列の連結であり、たとえば \((0, 3, 2) \frown (1, 4, 5) = (0, 3, 2, 1, 4, 5)\) である。以上の原始数列を用いて、\(P^{10}(9)~(P(n)=(0,\cdots,n)[n])\) と定義される数を原始数列数と定義する。

以上はベクレミシェフの虫になぞらえられた数学的定義である。ベクレミシェフの虫とは \(g\) と \(b\) に分割する位置が 1 ずれていることに注意すべきである。

定義の説明[]

\(i\) の見つけ方を分かりやすく言うと、「\(S_k\) よりも小さい数」を数列の右から探していって、初めてみつかった「\(S_k\) よりも小さい数」のインデックスを \(i\) とする、ということである。例えば、\((0, 1, 2, 3, 3, 1, 2, 3, 2, 3, 2, \underbrace{2}_{=S_k})[2]\) の場合は、\(S_k=2\) であり、\(2\) よりも小さな数をそこから左に探していって、初めて出てくるのが右側の \(S_5=1\) となるので、\(i=5\) となる。よってこの場合 \(b\) と \(g\) はそれぞれ \((\underbrace{0, 1, 2, 3, 3}_{=g}, \underbrace{1, 2, 3, 2, 3, 2}_{=b}, 2)[2]\) のようになる。そしてブラケットは \([2]\) であり、 \(f(n)=n^2\) なので、

\begin{eqnarray*} S[2]&=&g\frown b~\underbrace{\frown b\frown b\frown b\frown b}_{2^2~{\rm 個}}[2^2]\\ &=&(\underbrace{0, 1, 2, 3, 3}_{=g}, \underbrace{1, 2, 3, 2, 3, 2}_{=b}, \underbrace{1, 2, 3, 2, 3, 2}_{=b}, \underbrace{1, 2, 3, 2, 3, 2}_{=b}, \underbrace{1, 2, 3, 2, 3, 2}_{=b}, \underbrace{1, 2, 3, 2, 3, 2}_{=b})[4] \end{eqnarray*}

となる。また、この \(b\) の左端の要素 \(S_i\) はしばしば bad root と呼ばれる。

その他[]

原始数列は、原始数列システムを一般化させたバシク行列の書式として、\(S = (S_0 S_1 \ldots S_k) = (S_0)(S_1) \ldots (S_k)\) と書かれることが多い。

原始数列の計算は、バシク行列計算機で計算出来る。たとえば、(0)(1)(2)(3)[2] の計算結果はこのようになる（Maximum length を増やすと、さらに増える）。どんどん数列が長くなり、計算が終わらないように見えるが、この数列は必ず最後に空の数列となって、\([n]\) が残る。そこで、\([n]=n\) として計算が終了する。\(f(n)=n\) として、(0)(1)(2)[2]を計算すると、計算が終了するまでを見ることができる。

また、アルゴリズムを若干変えることで、原始数列の計算をハーディー階層と一致させることができ、このように \(H_{\omega^\omega}(2) = 8\) を計算させることができる。

関数 \(P(n) = (0,1,2, \ldots, n)[n]\) を考えると、\(P(n)\)の増加速度は \(f_{\varepsilon_0}(n)\) 程度である。原始数列数は \(P^{10}(9)\) であり、 \(f_{\varepsilon_0+1}(10)\) 程度である。

順序数との対応[]

原始数列は、\(\varepsilon_0\) よりも小さい順序数と次のように対応づけることができる。原始数列の計算では、計算が進むごとに必ず順序数が小さくなる。順序数の無限降下列は存在しないため、必ず計算が終了する。12AbBaがRoss Mathematics Programにて順序数崩壊関数に関する集中講義で原始数列の停止性の証明方法について入門的な概説を行い^[5]、みずどらも独立に原始数列の停止性を証明した^[6]。原始数列と対応する順序数を表示するプログラムは関連項目を参照。

順序数\(\alpha\)のヒドラツリーを書く。たとえば、上の図は Kirby and Paris (1982).^[7] の論文に解説されているように、\(\omega^{\omega^\omega+\omega^3}+\omega^{\omega^2+1}\) を表す。
ルートノード (root) からスタートする。
ルートノードから上に1つノードを上がる時には、数列の最後に新しい要素 0 を加える。
ノードを1つ上に上がる時には、数列の最後に「最後尾の要素の値 + 1」の値の要素を加える。
ノードの端点まで来たのでn個下の枝分かれのノードまで下がり、別の枝(segment)に進む時は、数列の最後に「最後尾の要素の値 - n + 1」の値の要素を加える。
すなわち各項の数字は対応するノードのルートノードを起点とした高さから1を引いた値となる。
以下はこの図での対応のさせ方の例である: \(\omega^{\omega^\omega}\)の部分は(0,1,2,3)というように表される。その後ノードを三本降りて、次の枝(segment)へ移り、(1,2,2,2)を得、列に追加される。その後、同様にして(0,1,2,2,1)が追加される。したがって、このヒドラツリーは数列(0,1,2,3,1,2,2,2,0,1,2,2,1)と対応する。
この対応を次のように表す: \(\omega^{\omega^\omega+\omega^3}+\omega^{\omega^2+1} = (0,1,2,3,1,2,2,2,0,1,2,2,1)\).

以下が、例である。

\begin{eqnarray*} 1 &=& (0) \\ 2 &=& (0,0) \\ 3 &=& (0,0,0) \\ \omega &=& (0,1) \\ \omega+2 &=& (0,1,0,0) \\ \omega \cdot 2 &=& (0,1,0,1) \\ \omega^2 &=& (0,1,1) \\ \omega^2+\omega &=& (0,1,1,0,1) \\ \omega^3 &=& (0,1,1,1) \\ \omega^\omega &=& (0,1,2) \\ \omega^{\omega^\omega} &=& (0,1,2,3) \\ \omega^{\omega^{\omega^\omega}} &=& (0,1,2,3,4) \\ \omega^{\omega^{(\omega^\omega+1)}} &=& (0,1,2,3,4,2) \\ \omega^{\omega^{\omega^{\omega^\omega}}} &=& (0,1,2,3,4,5) \\ \end{eqnarray*}

出典[]

↑ 作者のウィキアアカウント
↑ 作者のツイッターアカウント
↑ 巨大数探索スレッド10: 原始数列システムを計算するプログラムとその計算、そしてそれを説明するブログ記事
↑ 巨大数論
↑ Zongshu Wu, Ordinal Collapsing Functions, lecture note in Ross Mathematics Program, Google drive, 2023-07-09 (updated on 2024-06-16).
↑ みずどら原始数列の停止性証明 2024-07-30.
↑ Kirby, L.; Paris, J. (1982), "Accessible independence results for Peano arithmetic"