Ackermann function

The Ackermann function works as follows:

One may have noticed that addition, multiplication, and exponentiation seem to increase in “power”, that is, when pitted against each other, it is easier to produce enormous numbers with exponentiation than with multiplication, and so on.

The Ackermann function produces a hierarchy of such growth operations, and ascends one step higher in the hierarchy each time.

Addition is the first operator in the hierarchy (though if we wanted, we could define addition as repeated succession and declare addition the second operator in the hierarchy). The next operator in the hierarchy is produced by iterating the previous element in the hierarchy. For instance, the next few operators in the hierarchy are multiplication, exponentiation, and tetration:

Multiplication is iterated addition: $A \cdot B = \underbrace{A + A + \ldots A}_{B \text{ copies of } A}$

Exponentiation is iterated multiplication: $A^B = \underbrace{A \times A \times \ldots A}_{B \text{ copies of } A}$.

($A ^ B$ is written $A \uparrow B$ in knuth up arrow notation.)

Tetration is iterated exponentiation.$A \uparrow\uparrow B = \underbrace{A^{A^{\ldots^A}}}_{B \text{ copies of } A}$ times.

$\uparrow^n$ just means $n$ up arrows, so we can also write tetration as: $A \uparrow^2 B = \underbrace{A \uparrow^1 (A \uparrow^1 (\ldots A))}_{B \text{ copies of } A}$

Now the pattern can be noticed and generalized, following the rule: $A \uparrow^n B = \underbrace{A \uparrow^{n-1} (A \uparrow^{n-1} (\ldots A))}_{B \text{ copies of } A}$

And now we can define the Ackermann function as $A(n) = n \uparrow^n n$.

This definition is relatively small, but the functions grow at incredible rates. Wait But Why has a good intuitive description of how incredibly fast tetration, pentation, and hexation grow, but by the time we get to $A(6)$, the Ackermann function already grows far more quickly than that. $A(1)=1$, $A(2)=4$, and $A(3)$ cannot be written in the universe, as it has enormously more digits than our universe has subatomic particles.

Interestingly enough, the Ackermann function grows faster than all primitive recursive functions. This is related to a rather deep connection between the consistency strength of a mathematical theory (which sorts of results they are capable of proving) and the slowest-growing function for which the theory cannot prove “this function is defined on all integers.”