アッカーマン関数の値

二重帰納法で定義された $A (m, n)$ について、 $A (1, n) = n + 2$ , $A (2, n) = 2 n + 3$ , $A (3, n) = 2^{n + 3} - 3$ のような各段の閉じた式を下の段から順に導き、初期値を変えた変種も含めて $B (3, 1)$ のような値を求められる

前提

原始再帰的定義と関数の値（大学院数学計算理論・ラムダ計算）

この技能までの道筋（15 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

小数の四則計算（算数計算と数のきまり）
分数のたし算・ひき算（算数計算と数のきまり）
分数のかけ算・わり算（算数計算と数のきまり）
小数と分数のまじった計算（算数計算と数のきまり）
逆算（□ を求める）（算数計算と数のきまり）
正負の数の加法・減法（中学数学数と式）
四則の混じった計算の順序（算数計算と数のきまり）
正負の数の乗除・累乗と四則混合（中学数学数と式）
分配法則を使った計算のくふう（算数計算と数のきまり）
文字式の計算（同類項・分配法則）（中学数学数と式）
1 次方程式の解き方（中学数学方程式）
連立方程式の解き方（加減法・代入法）（中学数学方程式）
等差数列・等比数列の一般項（数学B 数列）
数学的帰納法と一般項の推定（数学B 数列）
原始再帰的定義と関数の値（大学院数学計算理論・ラムダ計算）

説明

アッカーマン関数は、0 以上の整数 $m, n$ に対して
$A (0, n) = n + 1, A (m + 1, 0) = A (m, 1), A (m + 1, n + 1) = A (m, A (m + 1, n))$
で定められる関数で、 $m$ と $n$ の両方について帰納的に定義されています（二重帰納法）。この技能では、第 $m$ 段の関数 $n \mapsto A (m, n)$ の閉じた式を $m = 0, 1, 2, 3$ と下の段から順に導き、それを使って $A (3, n)$ のような値や、初期値を変えた変種の値を求めます。値が爆発的に大きくなる関数の振る舞いを具体的につかむための基本の計算です。

なぜそうしてよいのか

$m$ を 1 つ固定して $A_{m} (n) = A (m, n)$ と書くと、定義の 2・3 番目の式は
$A_{m + 1} (0) = A_{m} (1), A_{m + 1} (n + 1) = A_{m} (A_{m + 1} (n))$
となります。これは「 $A_{m + 1}$ は初期値 $A_{m} (1)$ から始めて、1 段下の関数 $A_{m}$ を 1 回ずつ適用していく数列」という原始再帰の形です。つまり、1 段下の閉じた式 $A_{m} (n)$ がわかっていれば、 $A_{m + 1}$ は $a_{0} = A_{m} (1)$ , $a_{n + 1} = A_{m} (a_{n})$ という漸化式で決まる数列で、前提の技能（小さい値の表から一般形を推定し帰納法で確かめる）でその一般項を求められます。

実際に下から順に解くと: $A_{0} (n) = n + 1$ なので $A_{1}$ は「 $A_{0} (1) = 2$ から 1 ずつ増える」等差数列で $A_{1} (n) = n + 2$ 。 $A_{2}$ は「 $A_{1} (1) = 3$ から 2 ずつ増える」等差数列で $A_{2} (n) = 2 n + 3$ 。 $A_{3}$ は「 $A_{2} (1) = 5$ から始めて $a \mapsto 2 a + 3$ をくり返す」数列で、 $a_{n + 1} + 3 = 2 (a_{n} + 3)$ より $a_{n} + 3$ は初項 $8$ 、公比 $2$ の等比数列となり $A_{3} (n) = 2^{n + 3} - 3$ 。どの段も「1 段下の関数を何回もくり返し適用する」ので、段が上がるごとに足し算 → 掛け算 → 累乗 → 累乗の塔と、増え方が一気に激しくなります。初期値や $A (0, n)$ を変えた変種でも、この「段ごとに 1 段下をくり返す」構造は同じなので、同じ手順で解けます。

手順

定義を段ごとの漸化式に書き直す: $A_{m + 1} (0) = (与えられた初期値)$ , $A_{m + 1} (n + 1) = A_{m} (A_{m + 1} (n))$
最下段 $A_{0} (n)$ の式を定義から読み取る
1 段上の初期値 $A_{m + 1} (0)$ を求め、漸化式 $a_{n + 1} = A_{m} (a_{n})$ を具体的に書く（ $A_{m}$ が $n + c$ なら等差、 $2 n + c$ なら $a_{n} + c$ を等比に直す）
$n = 0, 1, 2, \dots$ の値の表から一般項を推定し、数学的帰納法で確かめる
必要な段まで手順 3・4 をくり返す。閉じた式が求めにくい段では、1 段下の閉じた式に代入して値を順に計算する: $A_{m + 1} (n + 1) = A_{m} (A_{m + 1} (n))$

例題

0 以上の整数 $m, n$ に対し、関数 $B (m, n)$ を
$B (0, n) = n + 2, B (m + 1, 0) = 1, B (m + 1, n + 1) = B (m, B (m + 1, n))$
で定める。 $B (3, 3)$ を求めよ。

例題の解答

（手順 1） $B_{m} (n) = B (m, n)$ とおくと、 $B_{m + 1} (0) = 1$ , $B_{m + 1} (n + 1) = B_{m} (B_{m + 1} (n))$ 。

（手順 2）最下段は $B_{0} (n) = n + 2$ 。

（手順 3・4、 $m = 1$ ） $B_{1} (0) = 1$ , $B_{1} (n + 1) = B_{0} (B_{1} (n)) = B_{1} (n) + 2$ 。初項 1、公差 2 の等差数列なので $B_{1} (n) = 2 n + 1$ （ $n = 0$ で $1$ 、 $B_{1} (n) + 2 = 2 (n + 1) + 1$ で帰納法が進む）。

（手順 3・4、 $m = 2$ ） $B_{2} (0) = 1$ , $B_{2} (n + 1) = B_{1} (B_{2} (n)) = 2 B_{2} (n) + 1$ 。両辺に 1 を足すと $B_{2} (n + 1) + 1 = 2 (B_{2} (n) + 1)$ で、 $B_{2} (n) + 1$ は初項 2、公比 2 の等比数列。よって $B_{2} (n) = 2^{n + 1} - 1$ （ $n = 0$ で $1$ 、 $2 (2^{n + 1} - 1) + 1 = 2^{n + 2} - 1$ で帰納法が進む）。

（手順 5、 $m = 3$ ） $B_{3} (0) = 1$ から $B_{3} (n + 1) = B_{2} (B_{3} (n)) = 2^{B_{3} (n) + 1} - 1$ を順に計算する:
$B_{3} (1) = B_{2} (1) = 2^{2} - 1 = 3,$
$B_{3} (2) = B_{2} (3) = 2^{4} - 1 = 15,$
$B_{3} (3) = B_{2} (15) = 2^{16} - 1 = 65535.$

答え: $65535$

よくある誤り

上の段の初期値を下の段の初期値と同じだと思ってしまう誤り。標準のアッカーマン関数では $A (2, 0) = A (1, 1) = 3$ で、 $A (1, 0) = 2$ ではない。正しくは定義の 2 番目の式 $A (m + 1, 0) = A (m, 1)$ に従って段ごとに計算する
漸化式の入れ子の向きを取り違え、 $A (m + 1, n + 1) = A (m + 1, A (m, n))$ のように計算してしまう誤り。正しくは外側が 1 段下の関数で、 $A (m + 1, n + 1) = A (m, A (m + 1, n))$ （例えば $A (2, 1) = A (1, A (2, 0)) = A (1, 3) = 5$ ）
$a_{n + 1} = 2 a_{n} + 3$ の一般項を $a_{n} = 2^{n} a_{0} + 3 n$ のように足される定数をそのまま足し合わせてしまう誤り。正しくは $a_{n + 1} + 3 = 2 (a_{n} + 3)$ と変形して $a_{n} = 2^{n} (a_{0} + 3) - 3$ （ $A (3, n)$ では $a_{0} = 5$ より $2^{n + 3} - 3$ ）
閉じた式の指数をずらしてしまう誤り。 $A (3, n) = 2^{n + 3} - 3$ を $2^{n} - 3$ や $2^{n + 2} - 3$ とすると $A (3, 0) = 5$ と合わない。求めた式は必ず $n = 0$ の値と比べて確かめる

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

入口の問題

難易度 1（大学院の講義の例題レベル）
$N = {0, 1, 2, \dots}$ （ $0$ を含む）とし、関数 $B : N \times N \to N$ を、すべての $m, n \in N$ について次の式で定める。
$B (0, n) = n + 2,$
$B (m + 1, 0) = B (m, 1),$
$B (m + 1, n + 1) = B (m, B (m + 1, n)) .$
$B (2, 3)$ の値を求めよ。

この技能を使う問題

この技能の次に学べること

べきの塔の剰余（大学院数学計算理論・ラムダ計算）