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, x^y, Nest[x^# &, 1, y], .... f[4,x,y] can also be written Array[x &, y, 1, Power] and is sometimes called tetration and denoted x↑↑y.


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