FANDOM


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

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

定義

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

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

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

非負整数のリストである \(S = (S_0, S_1, \ldots, S_k)\) が原始数列である。 原始数列は、非負整数 \(n\) から非負整数 \(S[n]\) への関数として働き、\(S[n]\) の値は以下のように定められる。

  • \( ( )[n]=n \) 。
  • 数列の良い部分 (good part) \(g\) と悪い部分 (bad part) \(b\) を、下記のように決める。下記の \(i\) は \(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] = (g \frown b \underbrace{\frown b \frown \cdots \frown b}_{f(n) ~\mathrm{個の}~\frown b})[f(n)]\) とする。ここで、\(f(n)\) は \(f(n)=n^2\) である。

\(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 個}}\\ &=&(\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)\) 程度である。

順序数との対応


原始数列は、\(\epsilon_0\) よりも小さい順序数と次のように対応づけることができる。原始数列の計算では、計算が進むごとに必ず順序数が小さくなる。順序数の無限降下列は存在しないため、必ず計算が終了する。

なお、原始数列と対応する順序数を表示するプログラムが作成されている[5]

Hydra1

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

出典

  1. 作者のウィキアアカウント
  2. 作者のツイッターアカウント
  3. 巨大数探索スレッド10: 原始数列システムを計算するプログラムその計算、そしてそれを説明するブログ記事
  4. 巨大数論
  5. 原始数列と対応する順序数を表示するプログラム
  6. Kirby, L.; Paris, J. (1982), "Accessible independence results for Peano arithmetic"

関連項目