関数の一覧

このページには、増大度の分かっている関数に関しては増大度の低いものから高いものへと順番に並べます。増大度の不明な関数や、そもそも定義が存在しない関数も含まれます。

原始帰納関数

急増加関数で \(f_0(n)\) 以上 \(f_\omega(n)\) 未満

• 後者関数 \( = a+1 = f_0(n)\)
• 加算 \( = a+b > f_0(n)\)
• 乗算 \(= a*b > f_1(n)\)
• 冪乗 \(= a^b \approx f_2(n)\)
• 階乗 \(= n! \approx f_2(n)\)
• 指数階乗 \(\approx f_3(n)\)
• テトレーション \(= {^{b}a} \approx f_3(n)\)
• ワオ関数 \(= 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)\)

多重帰納関数

急増加関数で \(f_\omega(n)\) 以上 \(f_{\omega^\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)\)
• グラハム関数 \(= g_n \approx f_{\omega+1}(n)\)
• 膨張 \(\approx f_{\omega+1}(n)\)
• 乗算膨張 \(\approx f_{\omega+2}(n)\)
• 冪乗膨張 \(\approx f_{\omega+3}(n)\)
• 膨張テトレーション \(\approx f_{\omega+4}(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)\)
• チェーン表記 \(= \underbrace{n \rightarrow n \rightarrow \ldots \rightarrow n \rightarrow n}_n \approx f_{\omega^2}(n)\)
• S変換をn回繰り返した関数 \(\approx f_{\omega^2}(n)\)
• SS変換 (バージョン1) をn回繰り返した関数 \(\approx f_{\omega^2+1}(n)\)
• SS変換 (バージョン2) をn回繰り返した関数 \(\approx f_{\omega^3}(n)\)
• 拡張チェーン表記 \(= n \rightarrow_n n \approx f_{\omega^3}(n)\)
• C(n)関数 \(= C(n,n,n) \approx f_{\omega^3 + \omega}(n)\)
• 配列チェーン表記 \(\approx f_{\omega^5}(n)\)

\(f_{\omega^\omega}(n)\) から \(f_{\varepsilon_0}(n)\) まで

• 多変数アッカーマン関数 \(\approx f_{\omega^\omega}(n)\)
• 配列表記 \(\approx f_{\omega^\omega}(n)\)
• 拡張ハイパーE表記 \(xE\# \approx f_{\omega^\omega}(n)\)
• 矢印表記改 \(\approx f_{\omega^\omega}(n)\)
• s(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_{\psi_0(\Lambda)}(n)\)まで

注意：ここに書かれている近似値の多くはソースがありません。

• テトレーション配列未満のBEAF \(\approx f_{\varepsilon_0}(n)\)
• 連鎖E表記 \(E\text{^} \approx f_{\varepsilon_0}(n)\)
• 多重リストアッカーマン関数 \(\approx f_{\varepsilon_0}(n)\)
• m(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)\)
• m(m,n)変換 \(\approx f_{\zeta_0}(n)\)
• 亜原始数列 \(\approx f_{\psi_0(\Omega^{\omega})}(n)\) (ブーフホルツのψによる近似)
• 拡張連鎖E表記 \(xE\text{^}\)
• TREE関数 \(>\) \(\textrm{tree}\)関数 \(> f_{\psi_0(\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_{\psi_0(\Lambda)}(n)\)以上の増加速度を持つと予想される計算可能関数

• 降下段階配列表記
• 拡張ブーフホルツのψ関数に伴う順序数表記
• くまくまψ関数
• くまくま(大嘘)多変数ψ
• 多変数段階配列表記
• 四関数
• 弱亜ペア数列
• 亜原始ψ関数
• 三関数
• 横ネスト段階配列表記
• 肉ヒドラ数列
• 二関数
• 弱ハイパーペア数列
• ハイパー原始ψ関数
• TSS-ψ関数
• \(0\)-Y数列
• バシク行列システム
• タラノフスキーのC
• N原始
• Y数列
• \(\omega\)-Y数列

再帰的理論を対角化する計算可能関数

• loaderのD関数
• 有限約束ゲームの FPLCI と FPLCI と FLCI
• 欲張りクリーク列の USGCS と USGDCS
• 欲張りクリーク列の USGDCS₂
• レイバーのテーブル

計算不可能関数

• ビジービーバー関数 \(= \Sigma(n)\)
• オーダーmのビジービーバー関数 \(= \Sigma_m(n)\)
• クサイ関数(Ξ関数) \(= \Xi(n)\)
• Aarex Function
• ラヨ関数
• ふぃっしゅ関数バージョン7