アッカーマンの逆関数は Union Find や最小全域木、半群の区間積など様々な問題の計算量に現れます。この記事ではなぜアッカーマンの逆関数が現れるのかを感じやすくするために、分かりやすい形に変形したいと思います。

アッカーマンの逆関数を分かりやすい形にする

アッカーマンの逆関数 \(\alpha(y)\) とは、アッカーマン関数 \(A_n(x)\) の逆関数です。
注：\(\alpha\) は、\(x\) ではなく \(n\) に対する逆関数

アッカーマン関数 \(A_n(x)\) とは非負整数 \(n, x\) に対して$$A_n(x) = \begin{cases}
x + 1, & \text{ if }n = 0\\
A_{n-1}(1), & \text{ if }x = 0\\
A_{n-1}(A_n(x-1)), & \text{ otherwise }\\
\end{cases}$$で定義される関数です。三つ目の漸化式を繰り返し適用することで、\(A_{n}\) は \(A_{n-1}\) を \(x+1\) 個合成した$$\begin{align}A_{n}(x) &= \underbrace{(A_{n-1} \circ A_{n-1} \circ \cdots A_{n-1} \circ A_{n-1})}_{x+1 \text{個}} (1) \end{align}$$ の形で書けます。難しく見えますが、二つ目と三つ目の漸化式はこのことを厳密に書いただけです。

\(A_{n}(x)\) は \(n\) 層の再帰的な関数の合成によって定義されており、 \(n\) の増加に伴い、猛烈に大きくなります。
$$\begin{alignat}{3}
&A_1(x)&=&1+(\cdots+(1+(1+1))\cdots)&&= x+2 \\
&A_2(x)&=&2+(\cdots+(2+(2+1))\cdots)&&=2(x+3)-3 \\
&A_3(x)&=&2(\cdots(2(2+1))\cdots)-3&&=2^{x+3}-3 \\
&A_4(x)&= &\underbrace{2^{2^{\cdot^{\cdot^{2^{1+3}}}}}}_{x+1\text{個の}2}-3& &=\underbrace{2^{2^{\cdot^{\cdot^{2^2}}}}}_{x+3\text{個の}2}-3\\
\end{alignat}$$

逆関数を \(\alpha(y)=\min\{ n\ :\ A_n(1) ≥ y \}\) と定義します。また、\(x\) に対する逆関数として、\(y=A_n(x) \Leftrightarrow x=\alpha_n(y)\) とすると
\begin{align}
y&=\underbrace{(A_{n-1} \circ A_{n-1} \circ \cdots A_{n-1} \circ A_{n-1})}_{x+1 \text{個}} (1) \\
1&= \underbrace{(\alpha_{n-1} \circ \alpha_{n-1} \circ \cdots \alpha_{n-1} \circ \alpha_{n-1})}_{x+1 \text{個}} (y)
\end{align} である。後者の式より（おおよそ）
$$\alpha_n(x) = \begin{cases}
0, & \text{ if } x < 1\\
x-1, & \text{ n=0 }\\
\alpha_n(\alpha_{n-1}(x))+1, & \text{ otherwise }\\
\end{cases}$$となる。これを用いて
\begin{align}
\alpha(y) &=\min\{ n\ :\ A_n(1) \geq y \}\\
\Leftrightarrow \alpha(y) &= \min \{n\ : 1 ≥ \alpha_{n}(y)\}\end{align} と書ける。
\(\alpha_{n-1}(x)\) で \(x\) を移して \(1\) 未満となるような \(\alpha_{n-1}\) の適用回数が \(\alpha_n(x)\) である。また、\(\alpha_n(x) \leq 1\) となるような \(n\) がアッカーマンの逆関数の値である。

\(\alpha_n(x)\) を漸化式に従って順に計算すると（おおよそ）、
\begin{align}
\alpha_0 &= x-1\\
\alpha_1 &= x-2\\
\alpha_2 &= x/2\\
\alpha_3 &= \log_2(x)\\
\alpha_4 &= \log_2^*(x)\\
\end{align}である（最後は iterated logarithm）。このような形にすると、分かりやすいのではないだろうか？