アッカーマン関数（アッカーマンかんすう、英: Ackermann function、独: Ackermannfunktion）とは、非負整数 m と n に対し、 A ( m , n ) = { n + 1 ,  if  m = 0 A ( m − 1 , 1 ) ,  if  n = 0 A (...

三角関数: 正弦関数 (sin)、余弦関数 (cos)、正接関数 (tan)など。幾何学や、周期的な現象を記述するために使われる。 双曲線関数: 双曲正弦関数 (sinh)、双曲余弦関数 (cosh) など。三角関数に似た関係式を持つ。 逆双曲線関数: 双曲線関数の逆関数。 グーデルマン関数: 双曲線関数と逆三角関数の合成関数。...

原始再帰関数は全て全域再帰的であるが、全域再帰関数が全て原始再帰的とは言えない。アッカーマン関数 A(m,n) は全域再帰関数でありながら原始再帰的でない有名な例である。アッカーマン関数を使って、原始再帰関数が全域再帰関数の部分集合であるとする見方もある。この場合、関数が原始再帰的であるとは、その関数...

超階乗および階冪は階乗を拡張したものである。 アッカーマン関数は、どのような原始再帰関数よりも早く増大する帰納的関数の例である。すなわち、どのような原始再帰関数であっても、その引数が十分大きいならば、アッカーマン関数の方が値が大きくなる。 配列表記はコンウェイのチェーン表記および...

関数は原始再帰関数（原始帰納的関数）と密接な関連があり、その帰納的定義（後述）は原始再帰関数に基づいている。ただし、μ再帰関数が全て原始再帰関数とは言えない。そのような例としてアッカーマン関数がある。 また、ラムダ計算で記述される再帰関数やマルコフアルゴリズムで計算できる関数も同じである。...

アッカーマン関数（日本）を用いるのが最も主流となっている。 この表記は急増加関数で x → x x ≈ f ω 3 ( x ) {\displaystyle x\rightarrow _{x}x\approx f_{\omega ^{3}}(x)} と近似できる。 ちなみに多変数アッカーマン関数で...

アインシュタインテンソル アダマール行列 アッカーマン関数 アティヤ・シンガーの指数定理 アルキメデス順序 アルゴリズム アルティン加群 アルティン環 アレクサンダー多項式 飯高次元 伊藤の公式 伊藤の補題 伊藤積分 岩澤理論 ヴァシリエフ不変量 ヴァーマ加群 ヴァンデルモンド行列 ウィーナー過程...

アッカーマン関数の逆関数であることを証明したのはロバート・タージャンだった。それまで、操作毎の時間の上限はジョン・ホップクロフトとジェフリー・ウルマンが証明した O(log* n) とされていた。log* は重複対数であり、これも増加の遅い関数である（ただし、アッカーマン関数の逆関数ほどではない）。タージャンと...

とは、全ての原始再帰関数の集合、あるいは原始再帰関数で決定される全ての形式言語の集合である。これには、加算、乗算、冪乗、tetration などが含まれる。 原始再帰的でない関数の例としてアッカーマン関数があり、それにより PR が厳密に R に含まれることがわかる。 PR に属する関数は明示的に枚挙可能だが、R...

の多項式を表す。 一般的ではないが、更に発散速度の速い関数も存在する（アッカーマン関数 A(m, n) など）。逆に更に発散速度の遅い関数として、逆関数である逆アッカーマン関数 α(n) などもあり、実際にあるアルゴリズムの計算量の見積りとして出現する。この関数は上界こそないものの、非常に発散速度が遅いために実用的には定数と見なされる...

ヴィルヘルム・アッカーマン（Wilhelm Friedrich Ackermann, 1896年3月29日 - 1962年12月24日）はドイツの数学者。 計算理論での重要な例の一つであるアッカーマン関数を考案した。 アッカーマンは、1925年に2階のペアノ算術を弱めた体系の無矛盾性の証明を与え、ゲ...