アッカーマン関数の計算回数の公式を求めよう

はじめに

アッカーマン関数の計算回数を求めたいと昔から思っていた。爆発的に計算量が大きくなるという記述はwikipediaにも登場するが、具体的な回数や公式は特に載っていない。

与える数が大きくなると爆発的に計算量が大きくなるという特徴があり、性能測定などに用いられることもある。

アッカーマン関数 『フリー百科事典　ウィキペディア日本語版』より転載(2026/07/01 00:00 JST)

色々と調べた結果、 stackexchange に似た質問があり、その回答に答えが載っていた。
ここでは、それを自分なりに証明しつつ、具体的な値を計算する。

計算

また、この変形を上から順に変形①・②・③と呼ぶことにする

計算回数の定義

例

上記の表より、$RA(1,1)=4$

計算回数の公式

stackexchange によると、以下が成り立つ。

公式の証明

上の2行は、アッカーマン関数の定義からそのまま導けるため省略する。
3行目がやや難しいが、順を追って$A(m,n)$を変形してみる。

この3行目の変形を繰り返すことにより、より理解しやすい式にすることが出来る。

$$ \begin{align*} RA(m,n)&=1 + RA(m-1, A(m, n-1)) + RA(m, n-1) \\ &=1 + RA(m-1, A(m, n-1)) + 1 + RA(m-1, A(m, n-2)) + RA(m, n-2) \\ &=1 + RA(m-1, A(m, n-1)) + 1 + RA(m-1, A(m, n-2)) + 1 + RA(m-1, A(m, n-3)) + RA(m, n-3) \\ &\cdots \\ &=1+1+1+\cdots(1がn-1個)\cdots+1+1+1+RA(m-1, A(m, n-1))+RA(m-1, A(m, n-2))+\cdots+RA(m-1, A(m, 2))+RA(m-1, A(m, 1))+RA(m, 1) \\ &=(n-1) + \sum_{i=1}^{n-1} RA(m-1, A(m, i)) +RA(m, 1)\\ &=(n-1) + \sum_{i=1}^{n-1} RA(m-1, A(m, i)) +1 + RA(m-1, A(m, 0)) + RA(m, 0) \\ &=(n) + \sum_{i=0}^{n-1} RA(m-1, A(m, i)) + RA(m, 0) \\ &=(n) + \sum_{i=0}^{n-1} RA(m-1, A(m, i)) + 1 + RA(m-1,1) \\ &=(n+1) + \sum_{i=0}^{n-1} RA(m-1, A(m, i)) + RA(m-1,1) \\ \end{align*} $$

実際に計算してみよう

$$ \begin{align*} RA(0,n)&=1 \\ RA(1,n)&=(n+1) + \sum_{i=0}^{n-1} RA(0, A(1, i)) + RA(0,1) \\ &=(n+2) + \sum_{i=0}^{n-1} + RA(0, A(1, i)) \\ &=(n+2) + \sum_{i=0}^{n-1} 1　\\ &= (n+2) +n = 2n+2 \end{align*} $$


$RA(2,n)$からは少し複雑になってくる。

$$ \begin{align*} RA(2,n) &= (n+1) + \sum_{i=0}^{n-1} RA(1, A(2, i)) + RA(1,1) && \text{} \\ &=(n+1) + \sum_{i=0}^{n-1} RA(1, A(2, i)) + 4 && \text{$\because RA(1,1)=2\times1+2=4$} \\ &= (n+5) + \sum_{i=0}^{n-1} RA(1, A(2, i)) && \text{} \\ \end{align*} $$

アッカーマン関数の公式より、$ A(2, i) = 2i+3$であるから、
$$ \begin{align*} \cdots &= (n+5) + \sum_{i=0}^{n-1} RA(1, 2i+3) && \text{} \\ &= (n+5) + \sum_{i=0}^{n-1} 2(2i+3)+2&& \text{$\because RA(1,n) = 2n+2 $} \\ &= (n+5) + \sum_{i=0}^{n-1} (4i+8)&& \text{} \\ &= (n+5) + 8n+ 4\sum_{i=0}^{n-1} i&& \text{$\because 8$は$n$個・定数は外に出せる} \\ &= (n+5) + 8n+ 4\sum_{i=1}^{n-1} i&& \text{$\because i=0$のときシグマは$0$なので無視できる} \\ &= (n+5) + 8n+ 4(0.5 \times (n-1) \times n)&& \text{$\because$自然数の部分和の公式に$i-1$を代入} \\ &= n+5 + 8n + 4(0.5n^2-0.5n) \\ &= 9n + 5 +2n^2 - 2n\\ &= 2n^2 +7n +5 \end{align*} $$

$RA(3,n)$からはより複雑。
$$ \begin{align*} RA(3,n) &= (n+1) + \sum_{i=0}^{n-1} RA(2, A(3, i)) + RA(2,1) && \text{} \\ &=(n+1) + \sum_{i=0}^{n-1} RA(2, A(3, i)) + 14 && \text{$\because RA(2,1)=2+7+5=14$} \\ &= (n+15) + \sum_{i=0}^{n-1} RA(2, A(3, i)) && \text{} \\ &= (n+15) + \sum_{i=0}^{n-1} RA(2,2^{i+3}-3)&& \text{$\because A(3,n) = 2^{n+3}-3$} \\ &= (n+15) + \sum_{i=0}^{n-1} 2(2^{i+3}-3)^2 +7(2^{i+3}-3) +5&& \text{$\because RA(2,n) = 2n^2 +7n +5$} \\ &= (n+15) + \sum_{i=0}^{n-1} 2^{2i+7} -3(2^{i+5})+ 7(2^{i+3})+2&& \text{整理する} \\ &= \frac{2^{2n+7}-120\times2^n+9n+37}{3}&& \text{頑張って計算する} \\ \end{align*} $$

$RA(4,n)$以降は、アッカーマン関数そのものの増大ペースが大きすぎて、具体的な値を知ることは不可能であるが、時間があればnが小さい時の値を計算したい。