Notes

Chapter 4: Systems Based on Numbers

Section 3: Recursive Sequences


Ackermann functions

A convenient example is

f[1, n_] := n; f[m_, 1] := f[m - 1, 2]

f[m_, n_] := f[m - 1, f[m, n - 1] + 1]

The original function constructed by Wilhelm Ackermann around 1926 is essentially

f[1, x_, y_] := x + y;
f[m_, x_, y_] := Nest[f[m - 1, x, #] &, x, y - 1]

or

f[m_, x_, y_]:= Nest[Function[z, Nest[#, x, z - 1]] &, x + # &, m - 1][y]

For successive m (following the so-called Grzegorczyk hierarchy) this is x + y, x y, xy, Nest[x# &, 1, y], .... f[4, x, y] can also be written Array[x &, y, 1, Power] and is sometimes called tetration and denoted xy.



Image Source Notebooks:

From Stephen Wolfram: A New Kind of Science [citation]