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.

About these ads

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)

    http://codepad.org/QdneSl1Q

  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

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

  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
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 612 other followers

%d bloggers like this: