p = 0
addition
Straight addition. The third argument is switched off entirely, and n just counts up.
Wilhelm Ackermann · Göttingen · 1928
Five lines of definition. Three arguments, each from 0 to 6. 343 values, of which about sixty can be written down at all.
| m \ n | n = 0 | n = 1 | n = 2 | n = 3 | n = 4 | n = 5 | n = 6 |
|---|
select any cell
Pick a cell in the table to see how that value is built.
every digit fits on this page
a real machine can print all the digits
the number itself is unprintable
no digit count is knowable
not expressible in up-arrow notation
reading the third argument
addition
Straight addition. The third argument is switched off entirely, and n just counts up.
multiplication
n copies of m added together. The base case φ(m,0,1) = 0 is what makes it multiplication rather than something shifted.
exponentiation
n copies of m multiplied together. Base case 1. Still ordinary arithmetic — the largest value here is 6⁶ = 46 656.
towers
A power tower of n+1 copies of m. φ(3,3,3) = 3^3^3^3, which has 3 638 334 640 025 digits. The cliff starts here.
iterated towers
Tower-building, iterated. Each n takes the previous value and uses it as the height of a new tower. φ(2,2,4) is already a tower of 17 twos.
iterated level 4
Level 4, iterated. The second argument passed down is itself a level-4 value, so up-arrow notation can no longer be unrolled into a fixed shape.
iterated level 5
Level 5, iterated. Nothing here is describable except by naming the recursion that produces it, which is exactly the point of the construction.
Levels 0, 1 and 2 land exactly on addition, multiplication and exponentiation. Level 3 gives power towers: φ(m, n, 3) is a tower of n+1 copies of m. Past that, φ keeps climbing, but it drifts out of step with the standard hyperoperations by one — the base case φ(m, 0, p) = m adds a copy at every level. So φ(m, n, 4) is iterated tetration, but it is not pentation on the nose.
two arguments, Péter and Robinson
If someone says "the Ackermann function" today they almost always mean this two-argument version, which is the one used to demonstrate that a total computable function need not be primitive recursive. It is a different function from φ, but it climbs the same ladder. Here it is over the same 0–6 range, for m up to 4.
| m \ n | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| A(0, n) | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| A(1, n) | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| A(2, n) | 3 | 5 | 7 | 9 | 11 | 13 | 15 |
| A(3, n) | 5 | 13 | 29 | 61 | 125 | 253 | 509 |
| A(4, n) | 13 | 65 533 | 2^65536 − 3 | 2↑↑6 − 3 | 2↑↑7 − 3 | 2↑↑8 − 3 | 2↑↑9 − 3 |
A(m,n) = n+1 when m = 0; A(m−1, 1) when n = 0; otherwise A(m−1, A(m, n−1)). The row index m plays the part that p plays in φ. A(5,·) and A(6,·) are omitted because there is nothing to print: A(5,0) is already 65 533, and A(5,1) is a tower of 65 536 twos.
the cliff
Nothing in the table is approximate — every cell is a specific, finite integer. The problem is representational. φ(2, 4, 3) = 265 536 has 19 729 digits and prints in a fifth of a second. φ(2, 5, 3) is that number used as an exponent, so its digit count alone has 19 729 digits. One more step and there is no way to say how big the digit count is, only how to construct it. Three steps after that, up-arrow notation runs out too and all that is left is the recursion itself.
This is the point Ackermann was making. Every primitive recursive function has its growth bounded in advance by the structure of its own definition. φ does not: the third argument reaches into the definition and changes which operation is being iterated. That single move is what puts it outside the primitive recursive class, and it is why the shaded region in the table above marches left every time p goes up by one.
Definition follows Ackermann's 1928 paper Zum Hilbertschen Aufbau der reellen Zahlen, in the form given by the Encyclopedia of Mathematics. All values computed exactly with Python integers where the digit count allowed it; magnitude classes assigned from measured digit counts, not estimates. Symbol ◂ means "the value in the cell immediately to the left".