## 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

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.

Advertisements

Given how heavily recursive this function is, I went with Haskell instead of Python:

[…] Programming News: Ackermann’s Function 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. Read full story => Programming Praxis […]

Feel free to laugh at me. I tried to use visual C# for this. Stack overflow or there is some arbitrary stack limit where visual C# in its infinite wisdom decided I didn’t know what I was doing. Fun times

Toecutter: If your language doesn’t provide a sufficient stack, you must create your own stack; that’s the point of the exercise. A(4,1)=65533 should be within range of your function.

Ha! Ackermann’s function. At least this can computer A(4,2) in python

def ackermann(m, n):

while m >= 4:

if n == 0:

n = 1

else:

n = ackermann(m, n - 1)

m = m - 1

if m == 3:

return (1 << n + 3) - 3

elif m == 2:

return (n << 1) + 3

elif m == 1:

return n + 2

else:

return n + 1

`print ackermann(4,2)`

http://codepad.org/QdneSl1Q

http://jsfiddle.net/vcKdF/3248/

How about some q

A:{[m; n]

if [m ~ 0; : n+1];

$ [n ~ 0;

if [0 < m;

: A[m-1; 1]];

if [0 < n;

: A[m-1; A[m; n-1]]]];

};

My solution written in Go lang: https://gist.github.com/2942073

Using the closed form, recursion only is necessary for Ackerman(m, n) with m >= 4.