1. 序章

このチュートリアルでは、アッカーマン関数とその計算に関連する問題について説明します。

最初にその定義を調べ、入力の小さな値に対してその出力を計算します。 次に、反復べき乗とその反復に関する分析的な定義を提供します。

このチュートリアルの最後に、アッカーマン関数の定義を理解し、その固有の特性の理由を理解します。

2. アッカーマン関数の定義

アッカーマン関数は一般にで示され、よく知られている二変数です。 その2つの入力項は、任意の非負の整数値を想定できます。 したがって、アッカーマン関数は次のように定義されます。

この定義は本質的に単純です。 ただし、驚くべきことに、関数への入力が増えると、魅力的で予期しない動作が発生します。

3. 小入力のアッカーマン関数

定義自体は私たちにとってあまり有益ではないかもしれません:この関数を理解するための良い方法は、したがって、その値のいくつかを計算することです。 ここでは、入力の最小値から始めます。

、as、およびvarieの値を保持するテーブルを段階的に作成してみましょう。 最も単純なケースは、関数が次の値を想定する場合です。

2番目に単純なケースは、の場合です。この場合、関数は対応するセルの右上の値を想定します。 これは、直感的に、テーブルのセルに関して定義の2番目のケースに割り当てる意味です。

のいくつかの値を事前に計算し、それに応じて最初の2つの列を埋めることができます。 簡単にするために、次の行に対応する4行目までテーブルを埋めています。

4. 再帰の深さ

入力の値が高い場合、アッカーマン関数の計算はますます困難になります。 これが当てはまる理由を理解するために、比較的小さい入力値の解を段階的に計算する方法を研究することは理にかなっています。

たとえば、を計算するプロセスを見てみましょう。 と、は、分析定義の3番目のケースに該当します。 したがって、以下を計算する必要があります。

2番目の用語は関数自体の呼び出しであり、最初に解決する必要があります。 分析定義の3番目のケースに再び該当するため、次のように置き換える必要があります。

右端の演算子は、分析定義の2番目のケースに対応する形式になりました。 したがって、次のようになります。

最後の演算子は定義の最初のケースに対応するため、対応する値に置き換えることができます。

右端の演算子も私たちに知られており、次のように評価されます。

最後に、最初のケースの定義を再度適用すると、の値を見つけることができます。これをの値に割り当てます。 関数をプログラムとして定義すると、計算するには、その関数に対して6回の呼び出しを実行する必要がありました。

5. 不思議な方向へ転がる

への再帰呼び出しの数は非常に速く増加することに注意してください。 これが、実際、テーブルの5行目以降で観察される奇妙な動作の理由です。 これらは、次の場合に関連付けられる値です。

上の表で、二重矢印は、クヌースの表記法で表された反復べき乗を示しています。 以降、関数は常に非常に大きな数値に評価されるため、簡単に書き留めることができないことに注意してください。 その後の増分ごとに、反復されたべき乗をもう一度繰り返します

最後に、再帰が非常に深いため、Ackermann関数は、コンパイラーのパフォーマンスのメトリックとして頻繁に使用されます。 メモリの効率的な割り当てをテストするための優れたベンチマークでもあります

6. 結論

このチュートリアルでは、アッカーマン関数とその計算に関連する問題について学習しました。