バシク行列システム | |
---|---|
型 | 行列 |
基本関数 | \(n^2\) |
バシク行列システム (Bashicu matrix system) は、バシク[1]が2014年に考案した巨大数を生み出すアルゴリズムである[2][3]。1行行列(原始数列システム)は \(f_{\epsilon_0}(n)\) の強さを持つ。2行行列(ペア数列システム)は、\(f_{\psi_0(\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_0(\Omega_3+\psi_2(\Omega_3+\Omega_2))\)
のように表記する。
定義[]
2015年8月22日、バシクはバシク行列システムを用いた巨大数バシク行列数をプログラミング言語 BASIC の疑似言語によって定義した[4]。
バシクが作成したプログラムは実行を目的としたものではなかったので、ふぃっしゅっしゅが計算過程を表示するプログラム「バシク行列計算機」を作成し、そのプログラムはバシクによって動作が検証された。したがって、バシク行列の正式な定義はバシク行列計算機のソースコード[5][6]に記述されている。バシク行列計算機にはWebインターフェイスがある。プログラムには4つの n increment の設定がある。バシク行列のオリジナルの定義は "n = n * n" のオプションであり、その他のオプションはバリエーションである。Simulate Hardy function のオプションを使って計算すると、その計算は \(\epsilon_0\) 未満の順序数についてワイナー階層のハーディー関数と完全に一致する。
数学的な定義[]
バシク行列数を数式で書くと下記のようになる[7]。
\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\lt t)\\ 0 &(\mathrm{if}~y\geq 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|\exists a \gt 0 ( p=(P_{y-1})^a(x)) \land S_{py} \lt S_{xy} \} & (\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]\]
この結果は、バシク行列計算機の計算結果と一致する。
改良[]
バシクが2015年8月21日に定義したバシク行列の最初のバージョン(通称BM1)に対して、Hyp cos は 2016年4月28日に英語版 Talk page にて計算が終了しない例を示した。その後、バシクがバシク行列バージョン2 (BM2) をバシク行列数の BASIC プログラムとしてブログ記事で発表した[8]。また、バシクが解説スライドを作成した[9]。
その後、2018年6月12日に、バシクによって BM3 が定義された[10]が、6月29日にAlemagno12 によって停止しない例が示された[11]。その後、2018年8月28日にBubby3によって BM2 も停止しない例が示された。[12]
最終的に2018年9月1日にバシクによって定義が修正され、現在は BM4 となっている。
また、BM4 が生まれるまで、BM2.2, BM2.3, BM3.1, BM3.2 など亜種がたくさん提案された[13][14]。
停止性の証明[]
バシク行列の計算が常に終了するかどうか、という疑問は未解決であったが、黒羽カフカ[15]によって、2016年に巨大数探索スレッドへ一定の条件で計算が終了する証明の概略が投稿された[16]。しかし、その後の検討によれば、その証明は完全ではなかった[17]。
2018年11月11日にP進大好きbotはバシク行列を2行に限定したペア数列システムの停止性を証明した[18]。
大きさの評価[]
1行行列(原始数列システム)は \(f_{\epsilon_0}(n)\) の強さを持つ。2行行列(ペア数列システム)は、\(f_{\psi_0(\Omega_{\omega})}(n)\) の強さを持つ。
バシク行列はあまりにも強力なので、3行行列(トリオ数列システム)の増加速度の急増加関数による解析は困難であるが、ある程度までは解析されている[19][20][21][22][23]。
文献での紹介[]
バシク行列システムは下記の文献にて紹介されている。
- フィッシュ, "巨大数論 第2版", Next Publishing Authors Press, 2017[24]
- フィッシュ, "巨大数の世界", 数学セミナー, vol.58, No.7, pp.28-31, 日本評論社, 2019[25]
- 鈴木真治, フィッシュ, "討議 有限と無限のせめぎあう場所", 現代思想2019年11月号, 青土社, 2019[26]
- フィッシュ, "巨大数論発展の軌跡", 現代思想2019年11月号, 青土社, 2019
関連リンク[]
- 定義
- バシク, "BASIC言語による巨大数のまとめ", 巨大数研究 Wiki, ユーザーブログ, 2015年8月
- バシク行列システムの解説 by Bashicu
- Bashicu Matrix Calculator by Fish
- Hydra Viewer by koteitan (ペア数列までの計算を、ヒドラで表示できる。)
- BM4 完全解説 by koteitan (BM4 の擬似BASICプログラムの読解解説)
出典[]
- ↑ 作者のウィキアアカウント
- ↑ バシク行列計算機
- ↑ フィッシュ 「巨大数論発展の軌跡」『現代思想』2019年12月号. p. 19-28.
- ↑ バシク行列数
- ↑ バシク行列計算機のソースコード
- ↑ バシク行列のC言語による定義
- ↑ ユーザーブログ:Koteitan/バシク行列の数式的定義
- ↑ ユーザーブログ:BashicuHyudora/BASIC言語による巨大数のまとめ
- ↑ バシク行列システムの解説
- ↑ バシク行列バージョン3
- ↑ BM3の停止しない例
- ↑ BM2の停止しない例
- ↑ ユーザーブログ:Koteitan/バシク行列の亜種ルールの分類
- ↑ A list of all BMS_versions and their differences
- ↑ 黒羽カフカの巨大数研究wikiのユーザーページ
- ↑ 巨大数探索スレッド11.75: 152-155とコピー
- ↑ ユーザーブログ:KurohaKafka/バシク行列_計算可能性の証明(コメント欄参照)
- ↑ ペア数列システムの停止性の証明
- ↑ バシクによる解析
- ↑ 黒羽カフカによる解析
- ↑ Matthew による解析
- ↑ Aarex による解析
- ↑ バシク行列解析リンク by koteitan
- ↑ フィッシュ, "巨大数論 第2版", Next Publishing Authors Press, 2017
- ↑ 数学セミナー 2019年7月号
- ↑ 現代思想2019年11月号
関連項目[]
Aeton: おこじょ数・N成長階層
mrna: 段階配列表記・降下段階配列表記・多変数段階配列表記・横ネスト段階配列表記
Kanrokoti: くまくまψ関数・亜原始ψ関数・ハイパー原始ψ関数・TSS-ψ関数
クロちゃん: クロちゃん数(第一・第ニ・第三・第四)
じぇいそん: ふにゃふにゃぜぇたかんすう・\(\zeta\)関数
たろう: 多変数アッカーマン関数・2重リストアッカーマン関数・多重リストアッカーマン関数
Nayuta Ito: フラン数(第一形態・第二形態・第四形態改三)・N原始・東方巨大数4の規則の境界を突いた巨大数
バシク: 原始数列数・大数列数・ペア数列数・バシク行列システム
長谷川由紀路: 紅魔館のメイドナンバー・恋符マスタースパーク数・みくみく順序数
108Hassium: E2:B-01-Hs・L-階差数列類・E3:B-02-Hs
公太郎: 弱亜ペア数列・肉ヒドラ数列・弱ハイパーペア数列
p進大好きbot: 超限急増加関数表記・拡張ブーフホルツのψ関数に伴う順序数表記・四関数・三関数・巨大数庭園数
ふぃっしゅ: ふぃっしゅ数(バージョン1・バージョン2・バージョン3・バージョン4・バージョン5・バージョン6・バージョン7)・ マシモ関数・マシモスケール・TR関数(I0関数)
ゆきと: 亜原始数列・ハイパー原始数列・Y数列
本: 巨大数論・寿司虚空編
大会: 東方巨大数・幻想巨大数・即席巨大数・式神巨大数・お料理巨大数
掲示板: 巨大数探索スレッド
外部リンク: 日本語の巨大数関連サイト