アッカーマン関数

アッカーマン関数とは

アッカーマン関数（Ackermann function）は、主に非負整数を使って定義される関数です。この関数は、計算機科学や数学での計算の限界を示すものとして広く知られています。その特徴的な点は、大きな数を引数として与えた際に、計算量が爆発的に増加することです。これにより、アッカーマン関数は性能測定の一環としても利用されることがあります。

定義

アッカーマン関数は次のように定義されています。変数 m と n に対して、次のような場合分けが行われます。

• - m = 0 の場合: A(m, n) = n + 1
• - n = 0 の場合: A(m, 0) = A(m - 1, 1)
• - それ以外の場合: A(m, n) = A(m - 1, A(m, n - 1))

この定義は、原始再帰関数でないμ再帰関数の例として有名です。その結果、アッカーマン関数は、計算可能性の理論における重要な事例となりました。

歴史的背景

アッカーマン関数の発展には、1920年代後半に活躍した数学者たちが関与しています。ダフィット・ヒルベルトの指導を受けていた学生、ガブリエル・スーダンとヴィルヘルム・アッカーマンは計算の基礎を研究しており、彼らの研究は、すべての計算可能関数が原始再帰的であるというヒルベルトの仮定を覆すものでした。

スーダンは1927年にスーダン関数を発表し、アッカーマンは1928年に3つの引数を必要とする関数を紹介しました。この関数は、スーダンやアッカーマンが全域計算可能関数の例でありながら、原始再帰的ではないことが注目されました。ヒルベルト自らがアッカーマン関数が原始再帰的でないと仮定しましたが、それはアッカーマンの証明によって裏付けられました。

概念

アッカーマンが発表した3変数関数は以下のように定義されています。ここで、引数 a、b、n を持っています。

• - φ(a, b, 0) = a + b
• - φ(a, 0, n + 1) は、n が 0 または 1 の場合は n を返し、それ以外では a を返します。
• - φ(a, b + 1, n + 1) = φ(a, φ(a, b, n + 1), n)

この定義により、アッカーマン関数の数値は急速に増加し、具体的に計算することが難しいことが特徴づけられます。

アッカーマン関数の具体値

アッカーマン関数の計算は、ある規則に従って行うことができ、一般的な形式では非常に大きな値を返します。例えば、次の関係を使うことで、A(m, n) を他の形で表すことが可能です。

• - A(m, n) = (2 ↑^(m−2) (n + 3)) - 3

このように、異なる記法を用いることで、アッカーマン関数の値を明示する方法が存在します。

逆アッカーマン関数

逆アッカーマン関数α(n)は、自然数 n に対して定義され、特定の条件を満たす m を見つけてその値を返す関数です。この関数もまた、計算量の分析に用いられることがあり、その成長は非常に遅いことが知られています。特に、ロバート・タージャンが提案した素集合データ構造において、逆アッカーマン関数の利用がなされています。

まとめ

アッカーマン関数は、計算可能性理論やコンピュータサイエンスにおいて、計算の限界を理解するための重要なツールとなっています。それにより、計算の複雑さや他の数学的関数との違いが明確になります。また、逆アッカーマン関数もその関連で重要な役割を果たしています。

もう一度検索