FANDOM


バシク行列システム
行列
基本関数 \(n^2\)
急増加関数 \(f_{>\psi(\psi_{I_\omega}(0))}(n)\)

バシク行列システム (Bashicu matrix system) は、バシク[1]が2014年に考案した巨大数を生み出すアルゴリズムである[2]。1行行列(原始数列システム)は \(f_{\epsilon_0}(n)\) の強さを持つ。2行行列(ペア数列システム)は、\(f_{\psi(\Omega_{\omega})}(n)\) の強さを持つ。3行行列 \begin{pmatrix}
 0 & 1 & 2 & 3  \\
 0 & 1 & 2 & 2  \\
 0 & 1 & 1 & 1
\end{pmatrix} は \(f_{\psi(\psi_{I_\omega}(0))}(n)\) の強さを持つ。n行行列 \begin{pmatrix}
 0 & 1 \\
 0 & 1 \\
 \vdots & \vdots \\
 0 & 1
\end{pmatrix} の増加速度は、急増加関数で対応する順序数が知られていない。その関数はローダー数で定義される関数よりは弱いと考えられている。

バシク行列には2つのバージョンがある[3]ペア数列システムは1つ目のバージョン BM1 と等価である。3行以上の BM1 は計算が終了しない場合があるため、3行以上では BM2 を使う。BM2 の計算方法を理解するのは大変なので、バシク行列の基本的なしくみを理解するためには、BM1 の理解から始めるのが良い。

定義 編集

記法 編集

バシク行列は、たとえば

\begin{pmatrix}
 a_{11} & a_{12} & a_{13}\\
 a_{21} & a_{22} & a_{23}
\end{pmatrix}

のような非負整数を要素に持つ行列で、これを \((a_{11},a_{21})(a_{12},a_{22})(a_{13},a_{23})\) のように列ベクトルの転置行列を並べて表記したものが、バシク行列の数列表記である。バシク行列 \(BM\) は、自然数 \(n\) から自然数 \(BM[n]\) への関数として働き、\((0,0)(1,1)(2,2)(3,3)(3,2)[n]\) のように書く。関数 \(BM[n]\) をハーディー階層によって増加速度を近似した時の順序数を \(\alpha\) としたとき、バシク行列 \(BM\) そのものが順序数 \(\alpha\) をあらわすものとする。すなわち、次のように表記できる。

\begin{pmatrix}
 0 & 1 & 2 & 3 & 3\\
 0 & 1 & 2 & 3 & 2
\end{pmatrix}
= (0,0)(1,1)(2,2)(3,3)(3,2) = \psi(\psi_1(\Omega_2))

変換ルール 編集

以下のルールは数列表記に対するものである。

用語 編集

  • 括弧の組の数(行列表記では行列の列数)を数列の長さと呼ぶ。
  • 長さが1の数列を数列の「要素」と呼ぶ。
  • \(S\): 任意長の数列。長さ0の数列を含む。 例:\((0,0,0)(1,1,1)(2,2,2)\)
  • \(Z = (0,0,...,0)\) (1個以上の0)
  • \(f(n) = n^2\) (この定義が基本であるが、この関数を変えたものもバシク行列システムのバリエーションであるとする)
  • \(A \frown B\) は数列の連結である。たとえば、\((0,0)(1,1) \frown (2,2)(3,3) = (0,0)(1,1)(2,2)(3,3)\) である。

計算ルール 編集

ここから先は BM1 について記す。

ルール1: \([n] = n\)

ルール2: \(S Z[n] = S[f(n)]\)

ルール3: ルール1と2が適用できないときには、以下のルールを順番に適用する。

ルール3-1: \(S = S_1 S_2 \ldots S_n\) を考える。ここで、\(S_i\) は数列\(S\)の要素であり、ルール2が適用されないため \(S_n \ne Z\) である。

ルール3-1-1: 最初、\(N=S_n=S'_n\) とする。また、\(N=(n_1,n_2,\cdots,n_h)\) とする(0でない一番下の値が \(n_h\) となっている)。

ルール3-1-2: \(N=S'_{i+1}\) のとき、\(\forall k<j(a_{ki}<n_k)\) が成り立つ最大の j について、\(S'_i=(a_{1i},a_{2i},\cdots,a_{(j-1)i},n_j,n_{j+1},\cdots,n_h)\) とし、 \(N=S'_i\) と \(N\) を更新する。

ルール3-1-3: このとき \(j-1=h\) であれば良い部分を \(S_1S_2\cdots S_{i-1}\) とし、悪い部分を \(S_iS_{i+1}\cdots S_n\) とする。そうでなければ ルール3-1-2 を繰り返す。

ルール3-2: \(L=S_i\)とおく。\(L = (L_0, L_1, \ldots ,L_m)\) と \(S_n = (N_0,N_1, \ldots ,N_m)\) から、\(\Delta = (\Delta_0, \Delta_1, \ldots ,\Delta_m)\) を次のように定める。

  • \(N_0,\ldots,N_{i+1}\) の中に 0 があれば \(\Delta_i = 0\) (\(N_{m+1}=0\) とする)。
  • そうでなければ \(\Delta_i = N_i - L_i\)とする。

ルール3-1によって \(\Delta_i \ge 0\) となる。

ルール3-3: B(i) を、次のように定義する。

  • \(B(0) = B\)
  • \(B(i+1)\) は、\(B(i)+\Delta\)。ここで、+は数値を足し算するという意味。たとえば、\(B(0) = (1,1,1)(2,2,2)(3,3,3)\), \(\Delta = (3,1,0)\) の時、B(1) = (4,2,1)(5,3,2)(6,4,3), B(2) = (7,3,1)(8,4,2)(9,5,3) となる。

ルール3-4: \(S[n] = \{ G \frown B(0) \frown B(1) \frown \ldots\ \frown B(f(n))\}[f(n)] \)

プログラムによる定義 編集

バシクはバシク行列をプログラミング言語BASICによって定義した。バシクが作成したプログラムは実行を目的としたものではなかったので、ふぃっしゅっしゅが計算過程を表示するプログラム「バシク行列計算機」を作成し、そのプログラムはバシクによって動作が検証された。したがって、バシク行列の正式な定義はバシク行列計算機のソースコード[4]に記述されている。このプログラムは BM1 と BM2 を両方計算できる[5]。バシク行列計算機にはWebインターフェイスがある。プログラムには4つの n increment の設定がある。バシク行列のオリジナルの定義は "n = n * n" のオプションであり、その他のオプションはバリエーションである。Simulate Hardy function のオプションを使って計算すると、その計算は \(\epsilon_0\) 未満の順序数についてワイナー階層のハーディー関数と完全に一致する。

計算例 編集

\((0,0,0)(1,1,1)(2,2,2)(3,3,3)(4,2,0)[2]\) を、上記ルールに従って計算する。

  • ルール3-1により、\(S = (0,0,0)(1,1,1)(2,2,2)(3,3,3)(4,2,0)\) として、\(S_4 = (4,2,0)\) よりも小さい要素で一番右のものを探すと、\(S_1 = (1,1,1)\) である。したがって、\(G = (0,0,0), B = (1,1,1)(2,2,2)(3,3,3), N = (4,2,0)\) となる。
  • ルール3-2により、 \(L = (1,1,1)\) と \(N = (4,2,0)\) に対して、\(\Delta = (3,0,0)\) と計算される。
  • ルール3-3により、 B(0) = (1,1,1)(2,2,2)(3,3,3), B(1) = (4,1,1)(5,2,2)(6,3,3), B(2) = (7,1,1)(8,2,2)(9,3,3), B(3) = (10,1,1)(11,2,2)(12,3,3), B(4) = (13,1,1)(14,2,2)(15,3,3) となる。
  • ルール3-4により \(S [2] = {G \frown B(0) \frown B(1) \frown B(2) \frown B(3) \frown B(4)} [4]\)

すなわち (0,0,0)(1,1,1)(2,2,2)(3,3,3)(4,2,0)[2] = (0,0,0)(1,1,1)(2,2,2)(3,3,3)(4,1,1)(5,2,2)(6,3,3)(7,1,1)(8,2,2)(9,3,3)(10,1,1)(11,2,2)(12,3,3)(13,1,1)(14,2,2)(15,3,3)[4] となる。これを行列の形で表記すると、このようになる。 \[\begin{pmatrix} 0 & 1 & 2 & 3 & 4\\ 0 & 1 & 2 & 3 & 2\\ 0 & 1 & 2 & 3 & 0\\ \end{pmatrix}[2] = \begin{pmatrix} 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15\\ 0 & 1 & 2 & 3 & 1 & 2 & 3 & 1 & 2 & 3 & 1 & 2 & 3 & 1 & 2 & 3 \\ 0 & 1 & 2 & 3 & 1 & 2 & 3 & 1 & 2 & 3 & 1 & 2 & 3 & 1 & 2 & 3 \\ \end{pmatrix}[4]\]

この結果は、バシク行列計算機の計算結果と一致する。

解析 編集

バシク行列の計算が常に終了するかどうか、という疑問はしばらく未解決であったが、黒羽カフカ[6]によって、2016年に巨大数探索スレッドへ一定の条件で計算が終了する証明の概略が投稿されたが[7]、 その後の検討によれば、その証明は完全ではなくまだバシク行列の計算が終了するかどうかは不明である[8]。この記事の英語版 Talk page で、2016年4月28日に Hyp cos が計算が終了しない例を示した。その後、バシクがバシク行列バージョン2 (BM2) をバシク行列数の BASIC プログラムとしてブログ記事で発表した[9]。バシク行列バージョン2では \begin{pmatrix}
 0 & 1 \\
 0 & 1 \\
 \vdots & \vdots \\
 0 & 1
\end{pmatrix} の計算が終了するであろうと期待されているが、その証明はまだ与えられていない。

1行行列(原始数列システム)は \(f_{\epsilon_0}(n)\) の強さを持つ。2行行列(ペア数列システム)は、\(f_{\psi(\Omega_{\omega})}(n)\) の強さを持つ。

バシク行列はあまりにも強力なので、3行行列(トリオ数列システム)の増加速度の急増加関数による解析は困難であるが、ある程度までは解析されている[10]。計算例を示す。

\begin{array}{ll} (0,0,0)(1,1,1)(2,2,1)(3,2,0) &=& ψ_0(ψ_I(0)) \\ (0,0,0)(1,1,1)(2,2,1)(3,2,1) &=& ψ(ψ_{I_ω}(0)) \\ (0,0,0)(1,1,1)(2,2,1)(3,3,1)(4,0,0) &=& \text{"Limit of Taranovsky's C"} \end{array}

n行バシク行列は「n階述語論理のある体系(n階のカインド)を対角化した強さ」であるとされる。バシク行列の計算が終了するのであれば、プログラムによって定義されていて、そのプログラムはチューリングマシンに翻訳可能なので、ビジービーバー関数よりは弱い。また、Thierry Coquand の calculus of constructions よりも弱いと考えられている。すなわち、loader.cで定義される関数よりは弱い。

出典 編集

  1. 作者のウィキアアカウント
  2. バシク行列計算機
  3. en:User blog:Kyodaisuu/Update of Bashicu Matrix Calculator
  4. バシク行列計算機のソースコード
  5. en:User blog:Kyodaisuu/Update of Bashicu Matrix Calculator
  6. ユーザー:KurohaKafka
  7. 巨大数探索スレッド11.75: 152-155コピー
  8. ユーザーブログ:KurohaKafka/バシク行列_計算可能性の証明(コメント欄参照)
  9. ユーザーブログ:BashicuHyudora/BASIC言語による巨大数のまとめ
  10. 作者による解析

関連項目 編集

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


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

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

FANDOMでも見てみる

おまかせWiki