Ackermann's function

Definition

$$ \array{ A(0,n) &= & n+1\\ A(m+1, 0) &=& A(m, 1) \\ A(m+1, n+1)& = &A(m, A(m+1, n)) } $$

Watch it grow

\begin{array}{r|rrrrrr} A(m,n) & n = 0& n = 1 &n = 2 &n = 3 &n = 4 &n = 5 \\\hline m = 0 &1 &2 &3 &4 &5 &6 \\ m = 1 &2 &3 &4 &5 &6 &7 \\ m = 2 &3 &5 &7 &9 &11 &13 \\ m = 3 &5 &13 &29 &61 &125 &253 \\ m = 4 &13 &65533 &2^{65536}-3 &2^{2^{65536}}-3 &A(3,2^{2^{65536}}-3) &A(3,A(4,4))\\ m = 5 &65533 &A(4,65533) &A(4,A(4,65533)) &A(4,A(5,2)) &A(4,A(5,3)) &A(4,A(5,4))\\ m = 6 &A(4,65533) &A(5,A(4,65533)) &A(5,A(6,1)) &A(5,A(6,2)) &A(5,A(6,3)) &A(5,A(6,4)) \end{array}

Ackermann's function, while Turing computable, grows faster than any primitive recursive function. The reason can be seen from the table: the index for the next value is also growing.

An equivalent definition

$$ A(0, n) = n + 1 \\ A(1, n) = 2 + (n + 3) - 3 \\ A(2, n) = 2 \times (n + 3) - 3 \\ A(3, n) = 2 n + 3 - 3 \\ A(4, n) = 2^{2^{\ldots^2}} - 3 \qquad (n + 3 \mbox{ terms}) \\ \ldots $$

remember that +++2^{2^{2^2}} = 2^{(2^{(2^2)})} = 65\,536+++, and not +++((2^2)^2)^2 = 2^{2 \times 2 \times 2} =256+++

Conventional mathematical notation breaks down at this point, and something more extensible is needed, invented specially to define big numbers.

• Cutland. Computability, section 2.5.5