FANDOM


色々と精査した結果、User_blog:Limitofempty/急増加関数とs(n)変換 の細かいところにミスがあることがわかり、修正しました。

訂正前に、具体的には以下の急増加関数の書き下し部分で間違えていました。繰り返し書いておきますが、この書き下しは間違いです。

\begin{align} f_{\omega \times 2}(3) =& f_{(\omega + \omega)[3]}(3) \\ =& f_{\omega + 3}(3) \\ =& f_{\omega + 2}^{3}(3) \\ =& f_{\omega + 1}^{27}(3) \\ =& f_{\omega}^{7625597484987}(3) \\ & \vdots \\ \end{align}

以上の書き下しは間違いです。ちなみに \(f_{\omega + 2}^{3}(3) = f_{\omega + 1}^{27}(3)\) の時点でおかしくなっています。このような法則はありません。後はこの間違いを前提に書き下しが続いていたので省略しています。

そこで以下が正しい書き下しです。

\begin{align} f_{\omega \times 2}(3) =& f_{(\omega + \omega)[3]}(3) \\ =& f_{\omega + 3}(3) \\ =& f_{\omega + 2}^{3}(3) \\ =& f_{\omega + 2}(f_{\omega + 2}(f_{\omega + 2}(3))) \\ =& f_{\omega + 2}(f_{\omega + 2}(f_{\omega + 2}(3))) \\ =& f_{\omega + 2}(f_{\omega + 2}(f_{\omega + 1}^3(3))) \\ =& f_{\omega + 2}(f_{\omega + 2}(f_{\omega + 1}(f_{\omega + 1}(f_{\omega + 1}(3))))) \\ =& f_{\omega + 2}(f_{\omega + 2}(f_{\omega + 1}(f_{\omega + 1}(f_{\omega}^3(3))))) \\ =& f_{\omega + 2}(f_{\omega + 2}(f_{\omega + 1}(f_{\omega + 1}(f_{\omega}(f_{\omega}(f_{\omega}(3))))))) \\ =& f_{\omega + 2}(f_{\omega + 2}(f_{\omega + 1}(f_{\omega + 1}(f_{\omega}(f_{\omega}((2^{402653184})402653184)))))) \\ =& f_{\omega + 2}(f_{\omega + 2}(f_{\omega + 1}(f_{\omega + 1}(f_{\omega}(f_{(2^{402653184})402653184}((2^{402653184})402653184)))))) \\ =& f_{\omega + 2}(f_{\omega + 2}(f_{\omega + 1}(f_{\omega + 1}(f_{\omega}(f_{(2^{402653184})402653184-1}^{(2^{402653184})402653184}((2^{402653184})402653184)))))) \\ & \vdots \\ \end{align}

もうわかりますが、ここから \(f_{\omega}^n(m)\) の形になる頃には、\(n\) が大変なことになります。メガフガスリーどころではありません。

これについて、[Prӧmel, et al., 1991] から参考になる部分を引用します。

For mappings \(F: \omega \rightarrow \omega\) we denote by \(F^n: \omega \rightarrow \omega\) the \(n\)-fold iterate of \(F, F^{n+1}(x) = F(F^n(x))\) where \(F^0(x) = x\). Consider the family \((F_k)_{k < \omega}\) of functions \(F_k: \omega \rightarrow \omega\) which is defined by

\[F_0(n) = n+1,\hspace 1em F_{k+1}(n) = F_k^n(n).\]

Note that the functions \(F_k\) speed up with a phantastic acceleration, e.g.,

\[F_1(n) = 2 \cdot n,\hspace 1em F_2(n) = 2^n \cdot n,\hspace 1em F_3(n) \geqslant 2^{\overbrace{2^{\cdot^{\cdot^{\cdot^{2^n}}}}}^{n\ twos}}.\]

アルファベットの大文字小文字が違う程度で、急増加関数と同じですね。そして重要なのは

\[F_3(n) \geqslant 2^{\overbrace{2^{\cdot^{\cdot^{\cdot^{2^n}}}}}^{n\ twos}}\]

という部分で、これはこの論文で stack-of-twos と呼ばれています。これを示すために、Code Ass さんが用意した \(f_2^m(n)\) を示す TeX の式を利用できます。これは寿司査読班での検証に用いられました(漫画で使うのかどうかは知りません)。ここの \(f_2^{10}(n)\) を展開したものを MathJax で処理すると、私の環境で 5 分ほどブラウザのタブが応答しなくなったので、とりあえずこれを少しいじって \(f_3(n)\) に対し \(n = 4\) までを示すと、以下のようになります。

\begin{align} f_3(1) = f_2^{1}(1) &= 2^1 1 \\ f_3(2) = f_2^{2}(2) &= 2^{2^2 2} {2^2 2} \\ f_3(3) = f_2^{3}(3) &= 2^{2^{2^3 3} {2^3 3}} {2^{2^3 3} {2^3 3}} \\ f_3(4) = f_2^{4}(4) &= 2^{2^{2^{2^4 4} {2^4 4}} {2^{2^4 4} {2^4 4}}} {2^{2^{2^4 4} {2^4 4}} {2^{2^4 4} {2^4 4}}} \end{align}

色々とおまけは増えますが、展開後の左端にある power tower の部分について、基本的な構造としては

\[\overbrace{2^{2^{\cdot^{\cdot^{\cdot^{2^n}}}}}}^{n\ twos}\]

であることがわかります。これにより、実際の \(f_3\) は stack-of-twos より右にあるおまけの分だけ更に大きくなりますが、そのおまけは 1 つ前の展開後の形がそっくりそのまま \(2^x x\) の \(x\) に入ってくることで構成されています。その結果、元の論文にある通り

\[F_3(n) \geqslant 2^{\overbrace{2^{\cdot^{\cdot^{\cdot^{2^n}}}}}^{n\ twos}}\]

という支配関係になります。

つまり、急増加関数で後続順序数を 3 下るだけでテトレーションレベルの大きさになるわけで、これが \(7625597484987\) などという小ささになるはずがありません。

ここで \(f_{\omega}(3)\) の書き下しについては先のエントリで以下のようになっていますが、これは正しいことを確認しています。

\begin{align} f_{\omega}(3) &= f_{\omega[3]}(3) \\ &= f_3(3) \\ &= f_2^3(3) \\ &= f_2^2((2^3)3) \\ &= f_2^2(24) \\ &= f_2((2^{24})24) \\ &= f_2(402653184) \\ &= (2^{402653184})402653184 \\ &\approx 6.895080597277195 \times 10^{121210694} \end{align}

これは書き下しを手でやらず、\(f_{\omega}(2) = 2^x x\) であることを利用したためにミスを回避できています。ちなみに一部を正確に手で書き下すと以下のようになります。

\begin{align} f_{\omega}(3) &= f_{\omega[3]}(3) \\ &= f_3(3) \\ &= f_2^3(3) \\ &= f_2(f_2(f_2(3))) \\ &= f_2(f_2(f_1^3(3))) \\ &= f_2(f_2(f_1(f_1(f_1(3))))) \\ &= f_2(f_2(f_1(f_1(f_0^3(3))))) \\ &= f_2(f_2(f_1(f_1(6)))) \\ &= f_2(f_2(f_1(12))) \\ &= f_2(f_2(24)) \\ &= f_2(f_1^{24}(24)) \\ &= f_2(\underbrace{f_1(f_1(f_1 \cdots f_1(}_{24 times}24\underbrace{) \cdots ))}_{24 times}) \\ &= f_2(\underbrace{f_1(f_1(f_1 \cdots f_1(}_{23 times}48\underbrace{) \cdots ))}_{23 times}) \\ &= f_2(\underbrace{f_1(f_1(f_1 \cdots f_1(}_{22 times}96\underbrace{) \cdots ))}_{22 times}) \\ &= f_2(\underbrace{f_1(f_1(f_1 \cdots f_1(}_{21 times}192\underbrace{) \cdots ))}_{21 times}) \\ &= f_2(\underbrace{f_1(f_1(f_1 \cdots f_1(}_{20 times}384\underbrace{) \cdots ))}_{20 times}) \\ &= f_2(\underbrace{f_1(f_1(f_1 \cdots f_1(}_{19 times}768\underbrace{) \cdots ))}_{19 times}) \\ &= f_2(\underbrace{f_1(f_1(f_1 \cdots f_1(}_{18 times}1536\underbrace{) \cdots ))}_{18 times}) \\ &= f_2(\underbrace{f_1(f_1(f_1 \cdots f_1(}_{17 times}3072\underbrace{) \cdots ))}_{17 times}) \\ &= f_2(\underbrace{f_1(f_1(f_1 \cdots f_1(}_{16 times}6144\underbrace{) \cdots ))}_{16 times}) \\ &= f_2(\underbrace{f_1(f_1(f_1 \cdots f_1(}_{15 times}12288\underbrace{) \cdots ))}_{15 times}) \\ &= f_2(\underbrace{f_1(f_1(f_1 \cdots f_1(}_{14 times}24576\underbrace{) \cdots ))}_{14 times}) \\ &= f_2(\underbrace{f_1(f_1(f_1 \cdots f_1(}_{13 times}49152\underbrace{) \cdots ))}_{13 times}) \\ &= f_2(\underbrace{f_1(f_1(f_1 \cdots f_1(}_{12 times}98304\underbrace{) \cdots ))}_{12 times}) \\ &= f_2(\underbrace{f_1(f_1(f_1 \cdots f_1(}_{11 times}196608\underbrace{) \cdots ))}_{11 times}) \\ &= f_2(f_1(f_1(f_1(f_1(f_1(f_1(f_1(f_1(f_1(f_1(393216))))))))))) \\ &= f_2(f_1(f_1(f_1(f_1(f_1(f_1(f_1(f_1(f_1(786432)))))))))) \\ &= f_2(f_1(f_1(f_1(f_1(f_1(f_1(f_1(f_1(1572864))))))))) \\ &= f_2(f_1(f_1(f_1(f_1(f_1(f_1(f_1(3145728)))))))) \\ &= f_2(f_1(f_1(f_1(f_1(f_1(f_1(6291456))))))) \\ &= f_2(f_1(f_1(f_1(f_1(f_1(12582912)))))) \\ &= f_2(f_1(f_1(f_1(f_1(25165824))))) \\ &= f_2(f_1(f_1(f_1(50331648)))) \\ &= f_2(f_1(f_1(100663296))) \\ &= f_2(f_1(201326592)) \\ &= f_2(402653184) \\ \end{align}

どうですか皆さん、模様って綺麗でしょう。

ここで、先程書いた「急増加関数で後続順序数を 3 下るだけでテトレーションレベルの大きさになるわけで、これが \(7625597484987\) などという小ささになるはずがありません」という言葉の通りになっています。これは \(6.895080597277195 \times 10^{121210694}\) に近似できる、すなわち \(121210694 + 1\) 桁の巨大数になりますが、ここで順序数を \(\omega \times 2\) にすると帰納的定義を展開していく中で更に \(\omega\) が登場し、\(f_{\omega}^n\) の形になる頃の \(n\) は \(121210694 + 1\) 桁どころではない更に大きな数へと爆発することになります。\(7625597484987\) では \(13\) 桁にしかならないので、根本的に大きさが違います。

また、件にエントリにおいてs(n)変換の書き下しにもミスがあります。これはまた別に修正を行い、解説を交えてエントリにします。また、s(n) 変換と急増加関数との間で比較を行っている部分は、すぐに直せないのでそのままにしてあります。そこもまとめて修正します。

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


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

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

FANDOMでも見てみる

おまかせWiki