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)\) の強さを持つ。n行行列 \((0,\cdots,0)(1,\cdots,1)\) の増加速度は、急増加関数で対応する順序数が知られていない。その関数はローダー数で定義される関数よりは弱いと考えられている。

記法

バシク行列は、たとえば

\(\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})\) のように列ベクトルの転置行列を並べて表記したものが、バシク行列の数列表記である。バシク行列 \({\boldsymbol S}[n]\) は、自然数 \(n\) から自然数 \({\boldsymbol S}[n]\) への関数として働き、\((0,0)(1,1)(2,2)(3,3)(3,2)[n]\) のように書く。関数 \({\boldsymbol S}[n]\) をハーディー階層によって増加速度を近似した時の順序数を \(\alpha\) としたとき、バシク行列 \({\boldsymbol S}\) そのものが順序数 \(\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))\)

定義

バシクはバシク行列システムを用いた巨大数バシク行列数をプログラミング言語 BASIC の疑似言語によって定義した[3]

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

数学的な定義

バシク行列数を数式で書くと下記のようになる[6]

\begin{eqnarray*} \mathrm{バシク行列数:}~K&=&\mathrm{Bm}^{10}(9)\\ \mathrm{巨大関数:}~\mathrm{Bm}(n)&=&\mathrm{expand}((\underbrace{0,0,\cdots,0}_{n+1})(\underbrace{1,1,\cdots,1}_{n+1})[n])\\ \mathrm{展開ルール:}~\mathrm{expand}([n])&=&n\\ \mathrm{expand}({\boldsymbol S}[n])&=&\left\{\begin{array}{ll} \mathrm{expand}({\boldsymbol S}_0\cdots{\boldsymbol S}_{X-2}[f(n)])&(\mathrm{if}~\forall y~S_{(X-1)y}=0)\\ \mathrm{expand}({\boldsymbol G}{\boldsymbol B}^{(0)}{\boldsymbol B}^{(1)}{\boldsymbol B}^{(2)} \cdots {\boldsymbol B}^{(f(n))}[f(n)])&(\mathrm{otherwise})\\ \end{array}\right.\\ \mathrm{活性化関数:}~f(n)&=&n^2\\ \mathrm{行列:}~{\boldsymbol S}&=&{\boldsymbol S}_0{\boldsymbol S}_1\cdots{\boldsymbol S}_{X-1}\\ \mathrm{列:}~{\boldsymbol S}_x&=&(S_{x0},S_{x1},\cdots,S_{x(Y-1)})\\ \mathrm{良い部分:}~{\boldsymbol G}&=&{\boldsymbol S}_0{\boldsymbol S}_1\cdots{\boldsymbol S}_{r-1}\\ \mathrm{悪い部分:}~{\boldsymbol B}^{(a)}&=&{\boldsymbol B}_0^{(a)}{\boldsymbol B}_1^{(a)}\cdots{\boldsymbol B}_{X-2-r}^{(a)}\\ \mathrm{悪い部分の列:}~{\boldsymbol B}_x^{(a)}&=&(B_{x0}^{(a)},B_{x1}^{(a)},\cdots,B_{x(Y-1)}^{(a)})\\ \mathrm{悪い部分の要素:}~B_{xy}^{(a)}&=&S_{(r+x)y}+a\Delta_{y}A_{xy}\\ \mathrm{上昇量:}~\Delta_{y}&=&\left\{\begin{array}{ll} S_{(X-1)y}-S_{ry}&(\mathrm{if}~y\gt t)\\ 0 &(\mathrm{if}~y\leq t) \end{array}\right.\\ \mathrm{上昇行列:}~A_{xy}&=&\left\{\begin{array}{ll} 1 &(\mathrm{if}~ \exists a( r=(P_{y})^a(r+x)))\\ 0 &(\mathrm{otherwise}) \end{array}\right.\\ \mathrm{非零最下行:}~t&=&\max\{y|S_{(X-1)y}\gt 0\}\\ \mathrm{bad root:}~r &=& P_t(X-1)\\ S_{xy}~\mathrm{の親}:~P_{y}(x)&=&\left\{\begin{array}{ll} \max\{p|p\lt x \land S_{py} \lt S_{xy} \land \exists a( p=(P_{y-1})^a(x))\} & (\mathrm{if}~y\gt 0)\\ \max\{p|p\lt x \land S_{py} \lt S_{xy} \} & (\mathrm{if}~y=0)\\ \end{array}\right.\\ \end{eqnarray*}

計算例

\((0,0,0)(1,1,1)(2,2,2)(3,3,3)(4,2,0)[2]\) を、上記ルールに従って計算する。 \begin{eqnarray*}{\boldsymbol S} &=& {\boldsymbol S}_0{\boldsymbol S}_1{\boldsymbol S}_2{\boldsymbol S}_3{\boldsymbol S}_4\\ &=&(S_{00},S_{01},S_{02})(S_{10},S_{11},S_{12})(S_{20},S_{21},S_{22})(S_{30},S_{31},S_{32})(S_{40},S_{41},S_{42})\\ &=&(0,0,0)(1,1,1)(2,2,2)(3,3,3)(4,2,0) \end{eqnarray*}

  • 1行目の:1行目最右列 \(S_{40} = 4\) よりも小さくて左にある最右要素は \(S_{30}=3\) である。このように、1行目にてある要素よりも小さくて左にある最右の要素を と呼ぶ。\(S_{xy}\) の親がいる列は \(P_y(x)\) と表される。
  • 直系先祖: 直系先祖の親か自分自身を、その要素の直系先祖 と呼ぶ。この場合、\(S_{40} = 4\) の直系先祖は \(S_{40}=4,~S_{30}=3,~S_{20}=2,~S_{10}=1,~S_{00}=0\) である。
  • 2行目以降の親: 2行目以降では、ある要素 \(S_{xy}\) に対して、その要素の一つ上の要素 \(S_{x,y-1}\) の直系先祖と同じ列 \((P_{y-1})^a(x)\) にあり、その要素 \(S_{xy}\) よりも小さくて左にあり最右の要素を親とする。
  • bad root: 非零最下行 \(t\) 最右列 \(X-1\) の親の列 \(P_t(X-1)\) を bad root \(r\) と呼び、それが複製されない良い部分 \({\boldsymbol G}\) と、複製される悪い部分 \({\boldsymbol B}^{(0)}\) の境目になる。この場合、2行目が非零最下行であり、bad root は2行目最右列 \(S_{41} = 2\) の親、つまり \(S_{11}=1\) であり、bad root は2行目 (\(r=1\)) となる。
  • 良い部分悪い部分: \({\boldsymbol S}_r = (1,1,1)\) となるので、\({\boldsymbol G} = (0,0,0), {\boldsymbol B}^{(0)} = (1,1,1)(2,2,2)(3,3,3)\) となる。
  • 上昇量: bad root \({\boldsymbol S}_r = (1,1,1)\) と刈られる子 \({\boldsymbol S}_{X-1} = (4,2,0)\) の値を用いて、上昇量は \((\Delta_0, \Delta_1, \Delta_2) = (3,0,0)\) と計算される。
  • 上昇行列は、bad root を直系先祖にもつ要素が 1 になる。この場合、\(A_{xy}=(1,1,1)(1,1,1)(1,1,1)\) となる。
  • 悪い部分の複製: これより悪い部分 \({\boldsymbol B}^{(a)}\) は \({\boldsymbol B}^{(0)} = (1,1,1)(2,2,2)(3,3,3)\), \({\boldsymbol B}^{(1)} = (4,1,1)(5,2,2)(6,3,3)\), \({\boldsymbol B}^{(2)} = (7,1,1)(8,2,2)(9,3,3)\), \({\boldsymbol B}^{(3)} = (10,1,1)(11,2,2)(12,3,3)\), \({\boldsymbol B}^{(4)} = (13,1,1)(14,2,2)(15,3,3)\) となる。
  • 展開ルールにより、\({\boldsymbol S}[2] = {\boldsymbol G}{\boldsymbol B}^{(0)}{\boldsymbol B}^{(1)}{\boldsymbol B}^{(2)}{\boldsymbol B}^{(3)}{\boldsymbol 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]\]

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

改良

英語版 Talk page で、2016年4月28日に Hyp cos が計算が終了しない例を示した。その後、バシクがバシク行列バージョン2 (BM2) をバシク行列数の BASIC プログラムとしてブログ記事で発表した[7]。また、バシクが解説スライドを作成した[8]

その後、2018年6月12日に、バシクによって BM3 が定義された[9]が、6月29日にAlemagno12 によって停止しない例が示された[10]。その後、2018年8月28日にBubby3によって BM2 も停止しない例が示された。[11]

最終的に2018年9月1日にバシクによって定義が修正され、現在は バージョン BM4 となっている。

また、BM4 が生まれるまで、BM2.2, BM2.3, BM3.1, BM3.2 など亜種がたくさん提案された[12][13]

停止性の証明

バシク行列の計算が常に終了するかどうか、という疑問は未解決であったが、黒羽カフカ[14]によって、2016年に巨大数探索スレッドへ一定の条件で計算が終了する証明の概略が投稿された[15]。しかし、その後の検討によれば、その証明は完全ではなかった[16]

2018年11月11日にP進大好きbotはバシク行列を2行に限定したペア数列システムの停止性を証明した[17]

大きさの評価

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

バシク行列はあまりにも強力なので、3行行列(トリオ数列システム)の増加速度の急増加関数による解析は困難であるが、ある程度までは解析されている[18][19][20][21][22]

出典

  1. 作者のウィキアアカウント
  2. バシク行列計算機
  3. BASIC言語による巨大数のまとめ バシク行列数
  4. バシク行列計算機のソースコード
  5. バシク行列のC言語による定義
  6. ユーザーブログ:Koteitan/バシク行列の数式的定義
  7. ユーザーブログ:BashicuHyudora/BASIC言語による巨大数のまとめ
  8. バシク行列システムの解説
  9. バシク行列バージョン3
  10. BM3の停止しない例
  11. BM2の停止しない例
  12. ユーザーブログ:Koteitan/バシク行列の亜種ルールの分類
  13. A list of all BMS_versions and their differences
  14. ユーザー:KurohaKafka
  15. 巨大数探索スレッド11.75: 152-155コピー
  16. ユーザーブログ:KurohaKafka/バシク行列_計算可能性の証明(コメント欄参照)
  17. ペア数列システムの停止性の証明
  18. バシクによる解析
  19. 黒羽カフカによる解析
  20. Matthew による解析
  21. Aarex による解析
  22. バシク行列解析リンク by koteitan

関連リンク

関連項目