Ackermann’s Function

May 25, 2012

In the 1920s, Wilhelm Ackermann demonstrated a computable function that was not primitive-recursive, settling an important argument in the run-up to the theory of computation. There are several versions of his function, of which the most common is

A(m,n) = \left\{    \begin{array}{ll}      n+1 & \mbox{if \(m=0\)} \\      A(m-1,1) & \mbox{if \(m > 0\) and \(n = 0\)} \\      A(m-1, A(m,n-1)) &        \mbox{if \(m > 0\) and \(n > 0\)}    \end{array}  \right.

defined over non-negative integers m and n. The function grows very rapidly, even for very small inputs; as an example, A(4,2) is an integer of about 20,000 digits.

Your task is to implement Ackermann’s function. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.


Pages: 1 2