| 横ベクレミシェフ | |
|---|---|
| 型 | 数列 |
| 急増加関数 | ≤\(f_{\Gamma_0}(n)\) |
横ベクレミシェフは、竹取翁が考案したアルゴリズムである[1]。特定の形の自然数列に対して基本列系を定める数列システムの一種である。
数列同士の辞書式順序による比較を用いるのが特徴である。
定義[]
数列の極限形としてどのような形を採用するかによって、定義の流儀が少し異なる。本記事では、極限形が(n)の形のものを扱う。
\begin{aligned}
\mathrm{クッパ横Bベク変数:} ~ K &= \mathrm{SB}^{5}(3) \\
\mathrm{巨大関数:} ~ \mathrm{SB}(n) &= \mathrm{expand}((n)[n]) \\
\mathrm{出力:} ~ [n] &= n \\
\mathrm{展開:} ~ \mathrm{expand}({\boldsymbol{S}}[n]) &= \left\{\begin{array}{ll}
\mathrm{expand}((a_k)_{k=1}^{\mathrm{Length}-1} [f(n)]) & (\mathrm{if} ~~ a_{\mathrm{Length}} = 0) \\
\mathrm{expand}({\boldsymbol G} \frown \underbrace{\boldsymbol{B} \frown \cdots \frown \boldsymbol{B}}_{f(n)個の\boldsymbol{B}} [f(n)]) & (\mathrm{otherwise}) \\
\end{array}\right. \\
\mathrm{活性化関数:} ~ f(n) &= n+1 \\
\mathrm{入力数列:} ~ {\boldsymbol S} &= (a_k)_{k=1}^{\mathrm{Length}} \\
\mathrm{良い部分:} ~ {\boldsymbol G} &= (a_k)_{k=1}^{\mathrm{tp}} \\
\mathrm{悪い部分:} ~ {\boldsymbol B} &= (a_k)_{k=\mathrm{tp}+1}^{\mathrm{Length}-1} \frown (a_{\mathrm{Length}}-1) \\
\mathrm{真親:} ~ \mathrm{tp} &= \left\{\begin{array}{ll}
\mathrm{p1} & (\mathrm{if} ~~ \mathrm{p1} = 0 ~ \lor ~ a_{\mathrm{p1}} \lt a_{\mathrm{Length}}-1) \\
\mathrm{p2} & (\textrm{else if} ~~ \mathrm{p2} = 0 ~ \lor ~ a_{\mathrm{p2}} \lt a_{\mathrm{Length}}-1) \\
\mathrm{p3} & (\mathrm{otherwise}) \\
\end{array}\right. \\
\mathrm{親3:} ~ \mathrm{p3} &= \mathrm{u}(\mathrm{p2}) \\
\mathrm{親2:} ~ \mathrm{p2} &= \mathrm{wp}(\mathrm{p1}) \\
\mathrm{親1:} ~ \mathrm{p1} &= \mathrm{wp}(\mathrm{Length}) \\
\mathrm{叔父:} ~ \mathrm{u}(x) &= \min(\set{i \in \mathbb{N} \setminus \set{0} \mid x \lt i \le \mathrm{Length} ~ \land ~ a_i = a_x} \cup \set{\mathrm{Length}}) \\
\mathrm{弱親:} ~ \mathrm{wp}(x) &= \max(\set{i \in \mathbb{N} \setminus \set{0} \mid i \le x \le \mathrm{Length} ~ \land ~ (a_k)_{k=i}^{\mathrm{Length}} < (a_k)_{k=x}^{\mathrm{Length}}} \cup \set{0}) \\
&※ただし、\mathrm{Length}は{\boldsymbol S}の長さとし、数列同士の大小比較は辞書式順序を採用する。
\end{aligned}
順序数拡張[]
可算順序数\(\alpha\)に対し、\(\alpha\)未満の極限順序数に可算基本列\([\ ]_o\)が定まっているとする。このとき、上記の定義の「展開」の部分を、
\begin{aligned}
\mathrm{展開:} ~ \mathrm{expand}({\boldsymbol{S}}[n]) &= \left\{\begin{array}{ll}
\mathrm{expand}((a_k)_{k=1}^{\mathrm{Length}-1} [f(n)]) & (\mathrm{if} ~~ a_{\mathrm{Length}} = 0) \\
\mathrm{expand}({\boldsymbol G} \frown \underbrace{\boldsymbol{B} \frown \cdots \frown \boldsymbol{B}}_{f(n)個の\boldsymbol{B}} [f(n)]) & (\textrm{else if} ~~ a_{\mathrm{Length}} は後続順序数) \\
\mathrm{expand}((a_k)_{k=1}^{\mathrm{Length}-1} \frown (a_{\mathrm{Length}}[f(n)]_o) [f(n)]) & (\mathrm{otherwise}) \\
\end{array}\right. \\
\end{aligned}
に書き換えることで、自然数の列だけでなく\(\alpha\)未満の順序数の列に対しても展開を行うことができる。このように、順序数列にまで拡張したアルゴリズムを「順序数拡張横ベクレミシェフ」とよぶ。
順序数拡張ベクレミシェフの展開規則は、数列内に現れる順序数の基本列系に依存する。
順序数との対応[]
対応方法[]
横ベクレミシェフ及びその順序数拡張は、停止性が証明されている[2]。
順序数拡張された(横でない)ベクレミシェフの虫を用いることで、大まかに以下のような手順で順序数に埋め込むことができる。
埋め込み写像を\(F\)と書くことにする。また、順序数列\(A\)はベクレミシェフの虫によって1つの順序数に対応するので、それを\(BW(A)\)と書くことにする。また、数列\(A\)の全ての項に左から\(\alpha\)を足した数列を\(^{\alpha+}A\)と表すことにする。
- \(S\)の項が\(0\)のみである場合、\(F(S)\)は\(S\)の長さとする。
- \(S =\ ^{\omega^{1+\alpha}+}S'\)を満たす数列\(S'\)と順序数\(\alpha\)が存在する場合、\(F(S') = 1+\beta\)を満たす\(\beta\)が存在するので、\(F(S) = \varphi(1,\alpha,\beta)\)とする。ただし、\(\varphi\)は\(3\)変数\(\textrm{veblen}\)関数とする。
- 上記のどちらでもない場合、\(S =\ ^{1+}\mathcal S_0 \frown (0) \frown \cdots \frown (0) \frown\ ^{1+}\mathcal S_d\)を満たす列\(\mathcal S_0,\cdots,\mathcal S_d\)が存在する。\(F(S) = BW(F(\mathcal S_0),\cdots,F(\mathcal S_d))\)とする。
この写像\(F\)は順序埋め込みであるため、少なくとも\(F(A)\)は\(A\)に対応する順序数以上である。同型写像であると予想はされており、もし同型ならちょうど\(F(A)\)に対応する。
特に、\(F((\omega^{1+\alpha})) = \varphi(1,\alpha,0)\)となるので、\(\omega^{1+\alpha}\)未満の順序数のみを扱う横ベクレミシェフは\(\varphi(1,\alpha,0)\)以下の順序数に対応する。自然数のみ扱う横ベクレミシェフは、少なくとも\(\Gamma_0\)以下の順序数に対応する。
横ベクレミシェフを基本列系として採用した順序数表記を用いて順序数拡張横ベクレミシェフを定義し、それを更に基本列系として順序数拡張ベクレミシェフを定義し、...と繰り返した極限は、\(\varphi(2,0,0)\)以下の順序数に対応する。
計算例[]
\(F((1,1,0,1,1))\)
\(= BW(F(0,0),F(0,0))\)
\(= BW(2,2)\)
\(= \omega^{\omega^2}\)
\(F((\omega^3+2,\omega^3+2,\omega^3,\omega^3+2,\omega^3+1,\omega^3,\omega^3+2,\omega^3+1,\omega^3+2))\)
\(= \varphi(1,2,F((2,2,0,2,1,0,2,1,2)))\)
\(= \varphi(1,2,BW((F(1,1),F(1,0),F(1,0,1))))\)
\(= \varphi(1,2,BW((BW((F(0,0))),BW((F(0),F())),BW((F(0),F(0))))))\)
\(= \varphi(1,2,BW((BW((2)),BW((1,0)),BW((1,1)))))\)
\(= \varphi(1,2,BW((\omega^\omega,\omega+1,\omega^2)))\)
\(= \varphi(1,2,\varepsilon_{\varphi(\omega,0)\times\zeta_0})\)
対応例[]
| 横ベクレミシェフ | ベクレミシェフ | 順序数 |
|---|---|---|
| \((\underbrace{0,\cdots,0}_n)\) | \((\underbrace{0,\cdots,0}_n)\) | \(n\) |
| \((1)\) | \((1)\) | \(\omega\) |
| \((1,\underbrace{0,\cdots,0}_n)\) | \((1,\underbrace{0,\cdots,0}_n)\) | \(\omega+n\) |
| \((1,0,0,1)\) | \((1,0,1)\) | \(\omega\times2\) |
| \((1,0,0,1,\underbrace{0,\cdots,0}_n)\) | \((1,0,1,\underbrace{0,\cdots,0}_n)\) | \(\omega\times2+n\) |
| \((1,0,0,1,0,0,1)\) | \((1,0,1,0,1)\) | \(\omega\times3\) |
| \((1,0,0,1,0,0,1,0,0,1)\) | \((1,0,1,0,1,0,1)\) | \(\omega\times4\) |
| \((1,0,1)\) | \((1,1)\) | \(\omega^2\) |
| \((1,0,1,0,0,1)\) | \((1,1,0,1)\) | \(\omega^2+\omega\) |
| \((1,0,1,0,0,1,0,0,1)\) | \((1,1,0,1,0,1)\) | \(\omega^2+\omega\times2\) |
| \((1,0,1,0,0,1,0,1)\) | \((1,1,0,1,1)\) | \(\omega^2\times2\) |
| \((1,0,1,0,0,1,0,1,0,0,1,0,1)\) | \((1,1,0,1,1,0,1,1)\) | \(\omega^2\times3\) |
| \((1,0,1,0,1)\) | \((1,1,1)\) | \(\omega^3\) |
| \((1,1)\) | \((2)\) | \(\omega^\omega\) |
| \((1,1,0,0,1,1)\) | \((2,0,2)\) | \(\omega^\omega\times2\) |
| \((1,1,0,1)\) | \((2,1)\) | \(\omega^{\omega+1}\) |
| \((1,1,0,1,0,1,1)\) | \((2,1,2)\) | \(\omega^{\omega\times2}\) |
| \((1,1,0,1,0,1,1,0,1,0,1,1)\) | \((2,1,2,1,2)\) | \(\omega^{\omega\times3}\) |
| \((1,1,0,1,1)\) | \((2,2)\) | \(\omega^{\omega^2}\) |
| \((1,1,1)\) | \((3)\) | \(\omega^{\omega^\omega}\) |
| \((\underbrace{1,\cdots,1}_n)\) | \((n)\) | \(\underbrace{\omega^{\omega^{\cdot^{\cdot^{\cdot^\omega}}}}}_n\) |
| \((2)\) | \((\omega)\) | \(\varepsilon_0\) |
| \((2,0,2)\) | \((\omega,\omega)\) | \(\varepsilon_1\) |
| \((2,1)\) | \((\omega+1)\) | \(\varepsilon_\omega\) |
| \((2,1,1)\) | \((\omega+2)\) | \(\varepsilon_{\omega^\omega}\) |
| \((2,1,1,2)\) | \((\omega\times2)\) | \(\varepsilon_{\varepsilon_0}\) |
| \((2,1,1,2,1,1,2)\) | \((\omega\times3)\) | \(\varepsilon_{\varepsilon_{\varepsilon_0}}\) |
| \((2,1,2)\) | \((\omega^2)\) | \(\zeta_0\) |
| \((2,1,2,0,2,1,2)\) | \((\omega^2,\omega^2)\) | \(\zeta_1\) |
| \((2,1,2,1)\) | \((\omega^2+1)\) | \(\zeta_\omega\) |
| \((2,1,2,1,1,2)\) | \((\omega^2+\omega)\) | \(\zeta_{\varepsilon_0}\) |
| \((2,1,2,1,1,2,1,2)\) | \((\omega^2\times2)\) | \(\zeta_{\zeta_0}\) |
| \((2,1,2,1,2)\) | \((\omega^3)\) | \(\varphi(3,0)\) |
| \((2,2)\) | \((\omega^\omega)\) | \(\varphi(\omega,0)\) |
| \((2,2,1,2)\) | \((\omega^{\omega+1})\) | \(\varphi(\omega+1,0)\) |
| \((2,2,2)\) | \((\omega^{\omega^\omega})\) | \(\varphi(\omega^\omega,0)\) |
| \((3)\) | \((\varepsilon_0)\) | \(\varphi(\varepsilon_0,0)\) |
| \((4)\) | \((\varphi(\varepsilon_0,0))\) | \(\varphi(\varphi(\varepsilon_0,0),0)\) |
| \((5)\) | \((\varphi(\varphi(\varepsilon_0,0),0))\) | \(\varphi(\varphi(\varphi(\varepsilon_0,0),0),0)\) |
| \((\omega)\) (通常の横ベクレミシェフの極限) | \((\Gamma_0)\) | \(\Gamma_0\) |
\(\mathfrak M\)-ベクレミシェフ[]
竹取翁は、巨大数列とベクレミシェフの虫、ベクレミシェフの虫と横ベクレミシェフの関係性を一般化することで、\(\mathfrak M\)-ベクレミシェフを定義した[3]。このアルゴリズムでは、\(0\)-ベクレミシェフが巨大数列システム、\(1\)-ベクレミシェフがベクレミシェフの虫、\(2\)-ベクレミシェフが横ベクレミシェフとなる。
これらは横ベクレミシェフと同様の手法で停止性を証明できると予想されている。この予想が正しければ、任意の\(\mathfrak M > 1\)について\(\mathfrak M\)ベクレミシェフは\(\varphi(\mathfrak M-1,0,0)\)以下の順序数に対応する。
出典[]
- ↑ 竹取翁, 横ベクレミシェフ, 巨大数研究 Wiki ユーザーブログ.
- ↑ みずどら, ベクレミシェフに関する予想, 巨大数研究 Wiki ユーザーブログ.
- ↑ 竹取翁, \(\mathfrak M\)-ベクレミシェフ, 巨大数研究 Wiki ユーザーブログ.