n-growing hierarchy

※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

 Fast-growing Hierarchyの応用で筆者が作成してみた成長階層表記です。FGHと同じく関数の大きさの評価にも使えると思いますが、どちらかというと数の大きさを評価する物差しとしての用途が主眼です。
 なお紛らわしくてごめんなさいなのですが、“n-growing hierarchy”という名称中の“n”は、下記定義中ではmに相当します。任意の自然数を種にして成長させる、という意味を込めた名称です。
 なお、長らくβ版としていましたが、これで正式版の定義ということにしようと思います。

定義

[m]_0(n)=m\times n

[m]_{\alpha+1}(n)=[m]^{n-1}_\alpha(m)
=\underbrace{[m]_\alpha([m]_\alpha(\dots([m]_\alpha}_{n-1}(m))\dots))

    ※ただし、n=1の時は、[m]_{\alpha+1}(1)=[m]^0_\alpha(m)=mとする。

[m]_\alpha(n) = [m]_{\alpha(n)}(m)

    ※αが極限順序数で、α[n]がαに対する収束列である時

定義の基礎的な部分はFast-growing Hierarchyを参照してまずはそちらを理解して下さい。


mには任意の整数を入れることが出来ます(ただし、m≦2だと上手く成長しません)。
例えばm=10であれば、“10-growing hierarchy”となり、以下の様になります。

[10]_0(n)=10\times n
[10]_{\alpha+1}(n)=[10]^{n-1}_\alpha(10)
[10]_\alpha(n) = [10]_{\alpha[n]}(10)

この成長階層は、少なくとも初期の段階では、タワー表記に‘ぴったし’一致します。
(というより、そうなるように定義を検討して作成しています。)

[10]_1(n)=10^n
[10]_2(n)=10\uparrow\uparrow n
[10]_m(n)=10\uparrow^m n
[10]_\omega(n)=10\uparrow^n 10=\{10,10,n\}

[10]_{\omega+1}(n)=\left\begin{matrix}{
10\underbrace{\uparrow\dots\uparrow}10 \\
10\underbrace{\uparrow\dots\uparrow}10 \\
\underbrace{\;\quad\vdots\quad\;} \\
10\underbrace{\uparrow\dots\uparrow}10 \\
10}\end{matrix}\right\}n=\{10,n,1,2\}

[10]_{\omega+2}(n)=\{10,n,2,2\}
[10]_{\omega+m}(n)=\{10,n,m,2\}
[10]_{\omega 2}(n)=\{10,10,n,2\}
[10]_{\omega 2+1}(n)=\{10,n,1,3\}
[10]_{\omega 2+m}(n)=\{10,n,m,3\}
[10]_{\omega 3}(n)=\{10,10,n,3\}
[10]_{\omega m}(n)=\{10,10,n,m\}
[10]_{\omega a+b}(n)=\{10,n,b,a+1\}
[10]_{\omega^2}(n)=\{10,10,10,n\}
[10]_{\omega^2+1}(n)=\{10,n,1,1,2\}
[10]_{\omega^2+m}(n)=\{10,n,m,1,2\}
[10]_{\omega^2+\omega}(n)=\{10,10,n,1,2\}
[10]_{\omega^2+\omega+1}(n)=\{10,n,1,2,2\}
[10]_{\omega^2+\omega+m}(n)=\{10,n,m,2,2\}
[10]_{\omega^2+\omega2}(n)=\{10,10,n,2,2\}
[10]_{\omega^2+\omega m}(n)=\{10,10,n,m,2\}
[10]_{\omega^2+\omega a+b}(n)=\{10,n,b,a+1,2\}
[10]_{\omega^2 2}(n)=\{10,10,10,n,2\}
[10]_{\omega^2 m}(n)=\{10,10,10,n,m\}
[10]_{\omega^2 a+\omega b+c}(n)=\{10,n,c,b+1,a+1\}
[10]_{\omega^3}(n)=\{10,10,10,10,n\}

これ以上はまだ未計算です。 (array表記に一致し続けるかもしれないしどこかで一致しなくなるかも知れない)

Diagonal n-growing hierarchy

※表記を変更してみた

N_0(n) = n\times n
N_{\alpha+1}(n) = N^{n-1}_\alpha(n)
N_\alpha(n) = N_{\alpha[n]}(n)

n-growing hierarchyの定義中の[m]に[n]を入れたものに相当し、[n]、(n)ともに増加させるようにしたものです。
[n]と(n)は同化して増加するため表記上から[n]を省いて関数記号Nと置き換えています。FGHもこれに割と近いものです(異なりますが)。
ふぃっしゅ氏がしばしば用いる「操作の対角化」って、おそらくこういうものだろうと思われます。
それ以外の規則や性質はn-growing hierarchyと同じです。

最終更新:2013年12月17日 08:13