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.

Posted by programmingpraxis

Filed in Exercises

10 Comments »

10 Responses to “Ackermann’s Function”

Graham said

May 25, 2012 at 10:15 AM

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

In the News: 2012-05-25 | Klaus' Korner said
May 25, 2012 at 1:28 PM
[…] 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 […]

slabounty said

May 25, 2012 at 10:19 PM

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)}"

toecutter said
May 26, 2012 at 1:31 AM
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
programmingpraxis said
May 26, 2012 at 1:13 PM
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.
iapain said
May 26, 2012 at 8:47 PM
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

cdelahousse said

May 26, 2012 at 11:17 PM

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/

igorii said
June 9, 2012 at 4:00 AM
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]]]]; };
Christian said
June 16, 2012 at 6:14 PM
My solution written in Go lang: https://gist.github.com/2942073

David Gottner said

September 14, 2013 at 2:13 PM

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

Programming Praxis