このページには、増大度の分かっている関数に関しては増大度の低いものから高いものへと順番に並べます。増大度の不明な関数や、そもそも定義が存在しない関数も含まれます。
原始再帰関数
急増加関数で \(f_0(n)\) 以上 \(f_\omega(n)\) 未満
- 後者関数 \( = a+1 = f_0(n)\)
- 加算 \( = a+b > f_0(n)\)
- 乗算 \(= a*b > f_1(n)\)
- 素数階乗\(= n\# < n! \approx f_2(n)\)
- 階乗 \(= n! \approx f_2(n)\)
- 下降階乗 \(= (n)_n = n! \approx f_2(n)\)
- 冪乗 \(= a^b \approx f_2(n)\)
- ローマ階乗 \(= \lfloor n \rceil ! \approx f_2(n)\)
- 下位階乗 \(= !n \approx f_2(n)\)
- 上昇階乗\(= n^{(n)} \approx f_2(2n)\)
- 二重指数関数 \(\approx f_2^2(n)\)
- 二重階乗 \(\approx f_2^2(n)\)
- 指数階乗 \(\approx f_3(n)\)
- テトレーション \(= {^{b}a} \approx f_3(n)\)
- 遡及階乗 \(\approx f_3(f_1(n))\)
- 超階乗\(=n\$ \approx f_3(f_2(n))\)(ただし、これはClifford Pickoverの定義した超階乗である。)
- ワオ関数 \(= 2 \uparrow \uparrow \uparrow n \approx f_4(n)\)
- ペンテーション \(= a \uparrow\uparrow\uparrow b \approx f_4(n)\)
- ヘキセーション \(= a \uparrow^{4} b \approx f_5(n)\)
- ヘプテーション \(= a \uparrow^{5} b \approx f_6(n)\)
- オクテーション \(= a \uparrow^{6} b \approx f_7(n)\)
- エンネーション \(= a \uparrow^{7} b \approx f_8(n)\)
- デケーション \(= a \uparrow^{8} b \approx f_{9}(n)\)
- ウンデケーション \(= a \uparrow^{9} b \approx f_{10}(n)\)
- ドデケーション \(= a \uparrow^{10} b \approx f_{11}(n)\)
- トリデケーション \(= a \uparrow^{11} b \approx f_{12}(n)\)
- ヴィジンテーション \(= a \uparrow^{18} b \approx f_{19}(n)\)
- ドヴィジンテーション \(= a \uparrow^{20} b \approx f_{21}(n)\)
- トリジンテーション \(= a \uparrow^{28} b \approx f_{29}(n)\)
- センテーション \(= a \uparrow^{98} b \approx f_{99}(n)\)
- センチトリエーション \(= a \uparrow^{101} b \approx f_{102}(n)\)
多重再帰関数
急増加関数で \(f_\omega(n)\) 以上 \(f_{\omega^\omega}(n)\) 未満
- 混成階乗(1変数)\(= n^* \approx f_\omega(n)\)
- アッカーマン関数 \(= A(n,n) \approx f_\omega(n)\)
- 矢印表記 \(= a \uparrow^{n} b \approx f_\omega(n)\)
- アッカーマン数 \(\approx f_\omega(n)\), ハイパー演算子の限界
- スタインハウス・モーザー表記 \(\approx f_\omega(n)\)
- ハイパーE表記 \(= E\# \approx f_\omega(n)\)
- 混成階乗(2変数)\({n^*}_n \approx f_{\omega+1}(n)\)
- グラハム関数 \(= g_n \approx f_{\omega+1}(n)\)
- 膨張 \(\approx f_{\omega+1}(n)\)
- 混成階乗(3変数)\({n^*}_{(n,n)} \approx f_{\omega+2}(n)\)
- 乗算膨張 \(\approx f_{\omega+2}(n)\)
- 冪乗膨張 \(\approx f_{\omega+3}(n)\)
- 膨張テトレーション \(\approx f_{\omega+4}(n)\)
- 混成階乗(4変数)\({n^*}_{(n,n:n)} \approx f_{\omega \times 2}(n)\)
- 爆発 \(\approx f_{\omega \times 2+1}(n)\)
- コピー表記\(=n[n \#\# n]\approx f_{\omega \times 2+1}(n)\)
- 乗算爆発 \(\approx f_{\omega \times 2+2}(n)\)
- 冪乗爆発 \(\approx f_{\omega \times 2+3}(n)\)
- 爆発テトレーション \(\approx f_{\omega \times 2+4}(n)\)
- 爆轟 \(\approx f_{\omega \times 3+1}(n)\)
- ペントネーション \(\approx f_{\omega \times 4+1}(n)\)
- ヘキソネーション \(\approx f_{\omega \times 5+1}(n)\)
- ヘプトネーション \(\approx f_{\omega \times 6+1}(n)\)
- オクトネーション \(\approx f_{\omega \times 7+1}(n)\)
- エノネーション\(\approx f_{\omega \times 8+1}(n)\)
- デコネーション \(\approx f_{\omega \times 9+1}(n)\)
- ふぃっしゅ関数バージョン1 \(\approx f_{\omega \times N}(n) (N \approx f_{\omega^2+1}(63))\)
- チェーン表記 \(= \underbrace{n \rightarrow n \rightarrow \ldots \rightarrow n \rightarrow n}_n \approx f_{\omega^2}(n)\)
- ふぃっしゅ関数バージョン2 \(\approx f_{\omega^2 \times 63}(n)\)
- 拡張チェーン表記 \(= n \rightarrow_n n \approx f_{\omega^3}(n)\)
- C(n)関数 \(= C(n,n,n) \approx f_{\omega^3 + \omega}(n)\)
\(f_{\omega^\omega}(n)\) から \(f_{\varepsilon_0}(n)\) まで
- 配列チェーン表記 \(\approx f_{\omega^\omega}(n)\)
- 多変数アッカーマン関数 \(\approx f_{\omega^\omega}(n)\)
- 配列表記 \(\approx f_{\omega^\omega}(n)\)
- 拡張ハイパーE表記 \(xE\# \approx f_{\omega^\omega}(n)\)
- 矢印表記改 \(\approx f_{\omega^\omega}(n)\)
- 拡張配列表記 (2次元) \(= \{a,b (2) 2\} \approx f_{\omega^{\omega^2}}(n)\)
- 拡張配列表記 (多次元) \(= \{a,b (0,1) 2\} \approx f_{\omega^{\omega^{\omega}}}(n)\)
- 2重リストアッカーマン関数 \(\approx f_{\omega^{\omega^\omega}}(n)\)
- 超次元までのBEAF \(= \{a,b (\underbrace{0,0\ldots0,0,1}_{n}) 2\} \approx f_{\omega^{\omega^{\omega^\omega}}}(n)\)
\(f_{\varepsilon_0}(n)\) から\(f_\mathrm{EBO}(n)\)まで
EBO: 拡張ブーフホルツ順序数
注意：ここに書かれている近似値の多くはソースがありません。
- テトレーション配列未満のBEAF \(\approx f_{\varepsilon_0}(n)\)
- 連鎖E表記 \(E\text{^} \approx f_{\varepsilon_0}(n)\)
- 多重リストアッカーマン関数 \(\approx f_{\varepsilon_0}(n)\)
- パリス・ハーリントン写像 \(\mathrm{PH}(n+3,8)\approx f_{\varepsilon_0}(n)\)
- グッドスタイン関数 \(= G(n) \approx f_{\varepsilon_0}(n)\)
- ヒドラ関数 \(\approx f_{\varepsilon_0}(n)\)
- 原始数列システム \(\approx f_{\varepsilon_0}(n)\)
- 亜原始数列 \(\approx f_{\psi_0(\Omega^{\omega})}(n)\) (ブーフホルツのψによる近似)
- 横ベクレミシェフ \(\approx f_{\psi_0(\Omega^{\Omega})}(n)\) (ブーフホルツのψによる近似)
- 拡張連鎖E表記 \(xE\text{^}\approx f_{\psi_0(\Omega^{\Omega\times \omega})}(n)\) (ブーフホルツのψによる近似)
- TREE関数 \(>\) \(\textrm{tree}\)関数 \(> f_{\psi_0(\Omega^{\Omega^{\omega}})}(n)\) (ブーフホルツのψによる下界。ただし厳密には\(\textrm{tree}\)関数そのものではなく\(\textrm{tree}(1.00001n+2)\)の下界である)
- バードの配列表記
- H関数
- S関数
- U関数
- 段階配列表記 \(\approx f_{\psi_0(\Omega_\omega)}(n)\) (ブーフホルツのψによる近似)
- ハイパー原始数列 \(\approx f_{\psi_0(\Omega_\omega)}(n)\) (ブーフホルツのψによる近似)
- ペア数列システム \(\approx f_{\psi_0(\Omega_\omega)}(n)\) (ブーフホルツのψによる近似)
- SCG関数
- ブーフホルツのヒドラ \(\geq f_{\psi_0(\varepsilon_{\Omega_\omega + 1})}(n)\) (ブーフホルツのψによる近似)
- ドル関数
- 強配列表記(合意のとれた定義は確認されていない)
\(f_\mathrm{EBO}(n)\)以上の増加速度を持つと予想される計算可能関数
- 降下段階配列表記 \(\approx f_\mathrm{EBO}(n)\)
- 拡張ブーフホルツのψ関数に伴う順序数表記 \(\approx f_\mathrm{EBO}(n)\)
- くまくま3変数ψ関数
- くまくま4変数ψ関数
- くまくま(大嘘)多変数ψ
- 多変数段階配列表記
- 四関数
- 三関数
- 肉ヒドラ数列
- 二関数
- 横ネスト段階配列表記
- トリプルネスト段階配列表記
- \(\zeta\)関数
- 亜原始ψ関数
- 弱亜ペア数列
- N原始
- L-階差数列類
- ハイパー原始ψ関数
- TSS-ψ関数
- 弱ハイパーペア数列
- \(0\)-Y数列
- バシク行列システム
- タラノフスキーのC
- 大偽行列システム
- Y数列
- \(\omega\)-Y数列
- バシク三角行列システム
- 順序数行バシク行列
再帰的理論を対角化する計算可能関数
- loaderのD関数
- 有限約束ゲームの FPLCI と FPLCI と FLCI
- 欲張りクリーク列の USGCS と USGDCS
- 欲張りクリーク列の USGDCS2
計算不可能関数
- ビジービーバー関数 \(= \Sigma(n)\)
- オーダーmのビジービーバー関数 \(= \Sigma_m(n)\)
- クサイ関数(Ξ関数) \(= \Xi(n)\)
- Aarex Function
- ラヨ関数
- ふぃっしゅ関数バージョン7(定義に問題が見つかっている)