Mastering the Ackermann Function

Yesterday I came in touch with a curious, astonishing mathematical function. It’s called Ackermann function.

Mathematically speaking, it is a well-defined total function. That is, it has defined values for every integer input (= total function), and this value is not ambiguous (every input has one and one only possible output value) (= well-defined).

Speaking about computer science, this function is computable, but it’s not a primitive recursive function. In other words, you can implement an algorithm to express the function using while-loops (= computable), but still you cannot write an equivalent algorithm using only do-loops (= not primitive recursive). I suggest you to try this statement.

The function has this form:

As you can see, it’s form is fairly simple. But, even if it seems simple, its values explode quickly. A(4, 2), for example, has more than 19.000 digits.

Ackermann Function on the complex plane

Representation of the Ackermann Function on the complex plane

What I want to talk about is the possible implementation of such a function by means of a computer algorithm. I will use Python for the next examples, but the description is language-independent.

Recursive approach

The quicker approach to solving such a problem is by implementing a recursive algorithm, since the definition of the function itself is recursive. Let’s try with something like this:

import sys

def A(x, y):
  if x == 0:
    return y+1
  else:
    if y == 0:
      return A(x-1, 1)
    else:
      return A(x-1, A(x, y-1))

x = int(sys.argv[1])
y = int(sys.argv[2])

print "Result of A(%d, %d) is %d" % (x, y, A(x, y))

You will want to try it calling from command line:

python ackermann.py 4 2

You will face a brutal reality: this algorithm will not end for the input (4, 2), since it quickly reaches the maximum recursion depth provided by Python. We will get better results starting from lower inputs.

You will find that the maximum computable values, for each possible x are:

  • A(1, 997) = 999
  • A(2, 497) = 997
  • A(3, 6) = 509
  • A(4, 0) = 13

For every input (x, y) with x greater than 5 you will get no result, for each y. As you can see, the function quickly diverges in complexity when x = 3, and much more when x = 4.

What we can try to do is jump as much iterations as possible with a simple trick: saving already computed values in order to not compute them anymore. This could simplify the navigation through the recursion graph.

Let’s try this implementation (with some debug information):

import sys

res = {}
jumps = 0
recursions = 0

#------ Start Method -------#
def A(x, y):
  global res, jumps, recursions

  recursions += 1
  try:
    jumps += 1
    return res[x][y]
  except Exception, e:
    jumps -= 1
    res[x] = {}

  if x == 0:
    res[x][y] = y+1
  else:
    if y == 0:
      res[x][y] = A(x-1, 1)
    else:
      res[x][y] = A(x-1, A(x, y-1))

  return res[x][y]
#------ End Method -------#

x = int(sys.argv[1])
y = int(sys.argv[2])

try:
  print "Result of A(%d, %d) is %d" % (x, y, A(x, y))
  print "%d total recursions, %d operations avoided" % (recursions, jumps)
except Exception, e:
  print "Exception occurred after %d recursions" % (recursions)

As you can see, the res variable is loaded with each computed value (at lines 20, 23, 25), and at the beginning of the function we try to return the value of A(x, y) if already computed (at line 14). The jumps variable keeps track of the number of the iterations saved by this implementation, while the recursions variable keeps track of the total number of single calls the the A function.

You can now still try to call the function to see what the maximum computable values are. You will find this:

  • A(1, 995) = 997
  • A(2, 496) = 995
  • A(3, 6) = 509
  • A(4, 0) = 13

We got three results: the maximum computable inputs have decreased ((1, 995) instead of (1,997) for example), the number of jumps increases with increasing values of the inputs, thus the computation time has decreased. Sadly, our target was not to reduce computable time, but reduce recursion depth.

We should try something different, to truly master the Ackermann Function. This something different involves computing the analytic form of the function. This approach will show a completely different world.

Probably I’ll talk about that in a future article. Let me know what you think about it, and submit your different implementations (different languages, different approaches) but still focusing on the recursion optimization.

30.442 thoughts on “Mastering the Ackermann Function

  1. I do accept as true with all the concepts you have offered for your post.
    They are very convincing and will certainly work.
    Nonetheless, the posts are very quick for newbies.
    May you please prolong them a bit from next time? Thank you for the post.

    Visit my website – 123movie

  2. My partner and I stumbled over here coming from a different page and thought I may
    as well check things out. I like what I see so now i
    am following you. Look forward to exploring your web page
    for a second time.

  3. I aam really impressed with your writing skills ass well as with the layout on your blog.
    Is this a paid theme or ddid you modify it yourself? Eitther waay keeep up the nice quality writing,
    it is rare to see a nice blog like this one these days.

    стероиды украина homepage анаболіки

  4. I’m curious to find out what blog system you’re working with?

    I’m experiencing some small security problems with
    my latest site and I’d like to find something more safeguarded.

    Do you have any recommendations?

  5. Have you ever thought about including a little bit more than just your
    articles? I mean, what you say is fundamental and all. Nevertheless imagine if you added some great images or videos to give your posts more, “pop”!
    Your content is excellent but with pics and
    clips, this blog could certainly be one of the greatest in its
    niche. Good blog!

    Look at my web blog: New Office Interior

  6. Aw, this was a really good post. Taking a few minutes and actual effort to make
    a very good article… but what can I say… I hesitate a lot and never
    seem to get nearly anything done.

  7. Simply wish to say your article is as astonishing. The clarity in your post is simply spectacular and
    i can assume you are an expert on this subject. Fine with your permission let me
    to grab your RSS feed to keep updated with forthcoming post.
    Thanks a million and please keep up the enjoyable work.

  8. I’ve been browsing online more than three hours nowadays, yet I never discovered any interesting article like yours.
    It is lovely worth enough for me. Personally, if all webmasters and bloggers made good content as you probably did,
    the net might be a lot more helpful than ever before.

    My website: 먹튀폴리스 (blip.fm)

  9. What i don’t realize is in reality how you’re not really a lot more well-preferred than you may be right now.
    You are very intelligent. You realize therefore considerably in relation to this topic, made me individually
    consider it from numerous varied angles. Its like men and women don’t seem to be interested
    until it’s one thing to accomplish with Girl gaga!

    Your personal stuffs great. At all times care for it up!

  10. Right here is the perfect website for anyone who really wants to
    find out about this topic. You know a whole lot its
    almost tough to argue with you (not that I personally will need to…HaHa).
    You certainly put a brand new spin on a subject which has been discussed for years.

    Excellent stuff, just wonderful!

  11. I’m truly enjoying the design and layout of your blog.
    It’s a very easy on the eyes which makes it much more pleasant for
    me to come here and visit more often. Did you hire out a designer to create your theme?
    Outstanding work!

    Feel free to surf to my web blog: 寫字樓設計

  12. Its like you learn my thoughts! You seem to know so much approximately this, like you wrote the guide
    in it or something. I believe that you could do with some percent to power the message house a little bit, however instead of that, that is
    excellent blog. A great read. I’ll certainly be back.

  13. I do believe all of the concepts you have introduced in your post.
    They are very convincing and can certainly work. Still, the posts
    are too quick for starters. May just you please extend them a bit from subsequent time?

    Thanks for the post.

    Feel free to visit my blog post … Personal Trainer

  14. Desperado rides more like a wooden coaster and can be rough but it’s no surprise I
    love it because of its history and I am a coaster enthusiast too.

    I don’t blame you for not liking it after getting beat up.As for the casino it used to be like a cool
    theme park kind of place but slowly was just let go. Who knows what will happen but I do hope it opens again.

  15. Hello I am so happy I found your blog page,
    I really found you by mistake, while I was searching on Digg for something
    else, Anyhow I am here now and would just like to say thank
    you for a fantastic post and a all round entertaining blog (I also love the theme/design), I don’t have time to
    browse it all at the minute but I have book-marked it
    and also added your RSS feeds, so when I have time I will be back
    to read a lot more, Please do keep up the awesome work.

  16. Admiring the time and effort you put into your site and detailed information you provide.
    It’s good to come across a blog every once in a while that
    isn’t the same old rehashed material. Fantastic read!
    I’ve bookmarked your site and I’m including your RSS feeds to my Google account.

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *