Fandom

巨大数研究 Wiki

原始数列数

548このwikiの
ページ数
新しいページをつくる
コメント11 シェアする

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

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

説明 編集

ベクレミシェフの虫になぞらえて説明する。非負整数のリストである \(S = (S_0, S_1, \ldots, S_n)\) が原始数列である。原始数列は、非負整数 \(n\) から非負整数 \(S[n]\) への関数である。ここで、原始数列システムを一般化させたバシク行列の書式では、\(S = (S_0 S_1 \ldots S_n) = (S_0)(S_1) \ldots (S_n)\) と書かれる。

\(S[n]\) を以下のように定める。 \(f(n)=n^2\) とおく。

  • \( ( )[n]=n \) 。
  • \(S_n = 0\) であれば、 \(S[n] = (S_0, S_1, \ldots, S_{n-1})[f(n)]\) とする。
  • そうでなければ、数列の良い部分 \(g\) と悪い部分 \(b\) を、次のように決める。ここで、\(S(n)\) は良い部分にも悪い部分にも属さない。\(i<n, S_i<S_n\) をみたす非負整数 \(i\) が存在するかどうかを考える。
    • \(i\) が存在しないときは \(g=(S_0, \ldots, S_{n−1}), b=( ) \) とする。
    • \(i\) が存在するときは \(k = \max \{i; i<n, S_i<S_n \}\) とおき、\(g=(S_0,\ldots,S_{k-1}), b= (S_{k},\ldots,S_{n-1})\) とする。ベクレミシェフの虫とは分割する位置が1ずれていることと、\(S_n\) がなくなっていることに注意。

そして、 \(S[n] = (g + b + b + \cdots + b + b)[f(n)]\) (\(f(n)+1\) 個の \(b\))とする。ここで、 + は数列の連結であり、たとえば \((0, 3, 2) + (1, 4, 5) = (0, 3, 2, 1, 4, 5)\) である。

原始数列数の計算は、バシク行列計算機で計算出来る。たとえば、(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\) よりも小さい順序数と次のように対応づけることができる。原始数列の計算では、計算が進むごとに必ず順序数が小さくなる。順序数の無限降下列は存在しないため、必ず計算が終了する。

Hydra1.jpg

  1. 順序数\(\alpha\)のヒドラツリーを書く。たとえば、上の図は Kirby and Paris (1982).[5] の論文に解説されているように、\(\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. Kirby, L.; Paris, J. (1982), "Accessible independence results for Peano arithmetic"

関連項目 編集

広告ブロッカーが検出されました。


広告収入で運営されている無料サイトWikiaでは、このたび広告ブロッカーをご利用の方向けの変更が加わりました。

広告ブロッカーが改変されている場合、Wikiaにアクセスしていただくことができなくなっています。カスタム広告ブロッカーを解除してご利用ください。

Fandomでも見てみる

おまかせWiki