# Ackermann function

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

The Ackermann function, expressed as $$A(a,b)$$, is a function for expressing extremely large numbers.

## Defination

The Ackermann function is defined as follows:

$$A(0,b)=b+1 \\ A(a,0)=A(a-1,1) \\ A(a,b)=A(a-1,A(a,b-1))$$

## Example

\begin{eqnarray*} A(4,3) &=& A(3,A(4,2)) \\ &=& A(3,A(3,A(4,1))) \\ &=& A(3,A(3,A(3,A(4,0)))) \\ &=& A(3,A(3,A(3,A(3,1)))) \\ &=& A(3,A(3,A(3,A(2,A(3,0))))) \\ &=& A(3,A(3,A(3,A(2,A(2,1))))) \\ &=& A(3,A(3,A(3,A(2,A(1,A(2,0)))))) \\ &=& A(3,A(3,A(3,A(2,A(1,A(1,1)))))) \\ &=& A(3,A(3,A(3,A(2,A(1,A(0,A(1,0))))))) \\ &=& A(3,A(3,A(3,A(2,A(1,A(0,A(0,1))))))) \\ &=& A(3,A(3,A(3,A(2,A(1,A(0,2)))))) \\ &=& A(3,A(3,A(3,A(2,A(1,3))))) \\ &=& A(3,A(3,A(3,A(2,A(0,A(1,2)))))) \\ &=& A(3,A(3,A(3,A(2,A(0,A(0,A(1,1))))))) \\ &=& A(3,A(3,A(3,A(2,A(0,A(0,A(0,A(1,0)))))))) \\ &=& A(3,A(3,A(3,A(2,A(0,A(0,A(0,A(0,1)))))))) \\ &=& A(3,A(3,A(3,A(2,A(0,A(0,A(0,2))))))) \\ &=& A(3,A(3,A(3,A(2,A(0,A(0,3)))))) \\ &=& A(3,A(3,A(3,A(2,A(0,4))))) \\ &=& A(3,A(3,A(3,A(2,5)))) \end{eqnarray*}

## Explicit formula

We now prove that $$A(a,b)=2\uparrow^{a-2}(b+3)-3$$ for $$a>2$$.

$A(0,b)=b+1 \\ A(1,b)=A(0,A(1,b-1))=A(1,b-1)+1=A(1,b-2)+2=\cdots=A(1,b-b)+b=b+2 \\ A(2,b)=A(1,A(2,b-1))=A(2,b-1)+2\times1=A(2,b-2)+2\times2=\cdots=A(2,b-b)+2b=2b+3=2(b+3)-3 \\ A(3,b)=A(2,A(3,b-1))=2(A(3,b-1)+3)-3=2^2(A(3,b-2)+3)-3=\cdots=2^b(A(3,0)+3)-3=2^{b+3}-3$

Assuming that this holds true for $$a=k$$, for $$a=k+1$$:

$A(k+1,b)=A(k,A(k+1,b-1))=2\uparrow^{k-2}(A(k,A(k+1,b-2)+3)-3=\cdots=\underbrace{2\uparrow^{k-2}2\uparrow^{k-2}\cdots\uparrow^{k-2}(A(k+1,0)+3)}_{\text{b 2's}}-3=\underbrace{2\uparrow^{k-2}2\uparrow^{k-2}\cdots\uparrow^{k-2}2\uparrow^{k-2}2}_{\text{b+3 2's}}-3=2\uparrow^{k-1}(b+3)-3$

QED.