The Ackermann function

While I was working on an article concerning the computability of pieces of the Riemann sphere, I read Cutland’s: Computability and found a curious function. The Ackermann function Eq. $\eqref{fxn:ackermann}$ is described as a non-primitively recursive function in chapter six of Cutland’s book. It is not until chapter ten that a satisfactory proof of recursion was given in the form of Kleene’s Recursion theorem.

\[\begin{equation} \label{fxn:ackermann} \begin{split} f(0,y) &= y + 1 \\ f(x+1,0) &= f(x,1) \\ f(x+1,y+1) &= f(x,f(x+1,y)) \end{split} \end{equation}\]

This function is curious given the nature of its two points of recursion. Given a background in computer science the complexity of this function was interesting to me. Specifically time complexity as given a large enough domain this small amount of logic could easily cause memory issues. However as a pure mathematical function this stills intrigues me. The amount of work done by this relatively short function is incredible to me. The function is able to traverse $\mathbb{N}^2$ in three recursive cases. Three steps that at first glance seems obvious, but if one stops to contemplate the logic it is marvelous. The function is computable as most programmers will assume at a glance (Church’s thesis), though the proof(s) is quite involved. As this is only a short post it is out of scope to go over the entirety of those proofs from Cutland. However to sketch the second one we begin with Kleene’s Recursion theorem [Cutland chapter ten]. This theorem describes computable recursive functions as those possessing “least fixed point” sub-functions. To significantly simplify and uncomplicated (that is, to lie) one could say that a least fixed point sub-function is that function of the form described by Eq. $\eqref{fxn:fixed-point}$. Kleene’s theorem states that this fixed point function is computable, thus the proof is to show that the Ackermann function is such a fixed point.

\[\begin{equation} \label{fxn:fixed-point} \begin{split} \text{Given that $f$ and $g$ are functions} \\ f(g) = g \begin{split} \end{equation}\]

I would be interested to explore the appearances of the Ackermann function in not just computer science but other fields. That is when is it useful to have either this or something like this kind of logical power. There is however always the chance that I have over reacted to this function given my proclivity for functional logic.