Ackermann functions

A convenient example is

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

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

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

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]

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]

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, x y

✖

x y, x^y

✖

\!\(\*SuperscriptBox[\(x\),\(y\)]\), Nest[x^# &, 1, y]

✖

Nest[\!\(\*SuperscriptBox[\(x\),\(#\)]\)&,1,y], .... f[4, x, y]

✖

f[4, x, y] can also be written Array[x &, y, 1, Power]

✖

Array[x &, y, 1, Power] and is sometimes called tetration and denoted x↑↑y

✖

x↑↑y.