## Ackermann’s Function

### May 25, 2012

Our function is a simple transliteration of the mathematical definition into code; note that in the second clause of the cond it is already known that m is zero:

(define (a m n)   (cond ((zero? m) (+ n 1))         ((zero? n) (a (- m 1) 1))         (else (a (- m 1) (a m (- n 1))))))

Here’s an example:

> (a 3 4) 125

You can run the program at http://programmingpraxis.codepad.org/lLpK9rFw.

Ackermann’s function was important in math, and is also important in computer science, being part of the computation of the time complexity of algorithms such as the disjoint-set data structure and others. It is also used as a test of recursion for compilers.

Pages: 1 2

### 10 Responses to “Ackermann’s Function”

1. Graham said

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

a :: Integer -> Integer -> Integer
a 0 n = n + 1
a m 0 = a (m - 1) 1
a m n = a (m - 1) $a m (n - 1) main :: IO () main = print$ a 3 4

2. […] 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 […]

3. slabounty said
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)}"

4. toecutter said

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

5. programmingpraxis said

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.

6. iapain said

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) 

7. 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/

8. igorii said

 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]]]]; }; 

9. Christian said

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

10. David Gottner said

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