巨大数研究 Wiki
登録
Advertisement

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

原始再帰関数

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

多重再帰関数

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

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

\(f_{\varepsilon_0}(n)\) から\(f_\mathrm{EBO}(n)\)まで

EBO: 拡張ブーフホルツ順序数

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

\(f_\mathrm{EBO}(n)\)以上の増加速度を持つと予想される計算可能関数

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

計算不可能関数

Advertisement