アッカーマン関数(アッカーマンかんすう、英: Ackermann function、独: Ackermannfunktion)とは、非負整数 m と n に対し、 によって定義される関数のことである。[1] 与える数が大きくなると爆発的に計算量が大きくなるという特徴があり、性能測定などに用いられることもある。 また、数学的な意味として、原始再帰関数でないμ再帰関数の実例として有名である。 歴史[編集] 1920年代後半、数学者ダフィット・ヒルベルトの教導を受けていた学生だったガブリエル・スーダン(英語版)とヴィルヘルム・アッカーマンは、計算の基礎を研究していた。ヒルベルトは、すべての計算可能関数が 原始再帰的であると仮定していた[要出典]。簡単に言えば、これは、コンピューターで計算できる各関数をいくつかの非常に単純なルールからまとめて、計算の期間を事前に推定できることを意味する。実際にこれ