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.
Programming Praxis 
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 […]
def a(m, n) if m == 0 n+1 elsif m > 0 && n == 0 a(m-1, 1) else a(m-1, a(m, n-1)) end end puts "ackerman 3, 4 = #{a(3, 4)}"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
function A(m,n) { return (m == 0) ? n + 1 : ( m > 0 && n ==0 ) ? A(m - 1,1) : ( m > 0 && n > 0) ? A(m - 1, A(m,n-1)) : undefined; }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.
def hyper(n, a, b) return b+1 if n == 0 return a+b if n == 1 return a*b if n == 2 return a**b if n == 3 return 1 if b == 0 x = a (b-1).times do |_| x = hyper(n-1, a, x) end return x end def ackerman(m, n) hyper(m, 2, n+3) - 3 end