Mastering the Ackermann Function

Posted on by marzapower

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.

50.697 thoughts on “Mastering the Ackermann Function”

  1. of course like your website however you have to take a look at the spelling
    on several of your posts. Many of them are rife with spelling problems and I find it
    very bothersome to inform the reality on the other hand I will definitely come
    again again.

    Rispondi

  6. of cߋurse like your web site but you neｅd to check
    thе spelling оn several off your postѕ. Several of hem are rife ѡith spelling issues and I in findіng it very bothersome
    tto inform the truth then agаin I will ceгtɑinly come aցain again.

    my website: pinjaman bri

    Rispondi

  7. Right here is the perfect website for everyone who wants to find out
    about this topic. You know a whole lot its almost
    hard to argue with you (not that I really would want to…HaHa).
    You certainly put a brand new spin on a subject
    that’s been discussed for many years. Wonderful stuff, just wonderful!

    Rispondi

  8. Hi, I do believe this is a great web site. I stumbledupon it 😉 I am going to return yet again since I book-marked it.
    Money and freedom is the best way to change, may you be rich and continue to help others.

    Rispondi

  11. Hey there exceptional blog! Does running a blog similar to this take a massive amount work?
    I’ve very little understanding of coding but I had been hoping to start my own blog in the near
    future. Anyhow, should you have any ideas or techniques for new blog owners please share.
    I know this is off topic but I simply had to ask. Thanks a lot!

    Rispondi

  13. I was wondering if you ever thought of changing the structure of your blog?
    Its very well written; I love what youve got to say. But maybe you could a little more in the way of content so people could connect
    with it better. Youve got an awful lot of text for only having 1
    or 2 pictures. Maybe you could space it out better?

    Also visit my blog: Blood Irradiation

    Rispondi

  14. jokerThe # 1 slot game is an app with a wide variety of games to choose from. Which has more than 100 items ever There are casino games to choose from, whether it is online slots, fish shooting, casino

    Rispondi

  15. pg auto Hot new online slots games in 2020 that will lead you into a whirlpool of playing online slots that have a completely new and unique game genre. Online access to 5 camps such as sexybaccarat, sagaming, aggaming, prettygaming, dreamgaming.

    Rispondi

  26. Hey there I am so delighted I found your webpage, I
    really found you by accident, while I was looking on Askjeeve for something else, Anyhow I am here now and
    would just like to say thanks for a incredible post and a all round thrilling blog (I also love the theme/design),
    I don’t have time to look over it all at the moment but
    I have book-marked it and also included your RSS feeds, so when I
    have time I will be back to read a lot more, Please do keep up the fantastic job.

    Rispondi

  27. It is appropriate time to make some plans for the future
    and it’s time to be happy. I’ve read this post
    and if I could I want to suggest you some interesting things or tips.
    Perhaps you can write next articles referring to
    this article. I wish to read even more things about it!

    Rispondi

  28. First of all I want to say fantastic blog! I had a quick question in which I’d like to ask if you don’t
    mind. I was curious to find out how you center yourself
    and clear your thoughts before writing. I’ve had difficulty clearing my mind
    in getting my thoughts out there. I do take pleasure in writing however it just seems like the
    first 10 to 15 minutes are wasted just trying to figure out how to
    begin. Any ideas or tips? Appreciate it!

    Here is my web blog: nha cai uy tin

    Rispondi

  30. Generally I do not learn article on blogs, but I would like to say that this write-up very
    forced me to take a look at and do it! Your writing
    taste has been surprised me. Thank you, quite great article.

    Rispondi

  33. I trսly love your ѡebsite.. Plеasant colors &
    theme. Did you develop this web ѕite yourself? Please relly
    baack as I’m wanting to create mү own personal webѕite and would likkｅ to learn wһere you got this from
    orr just ԝhat tthe thene is called. Many thanks!

    Feel free tօo surf to my web site: kunjungi website kami

    Rispondi

  38. After looking at a few of the blog articles on your website,
    I honestly appreciate your technique of blogging.

    I book marked it to my bookmark webpage list and will be
    checking back soon. Take a look at my web site too
    and tell me what you think.

    Rispondi

  50. This is really interesting, You’re a very skilled blogger.
    I’ve joined your rss feed and look forward to seeking more of your fantastic post.
    Also, I’ve shared your site in my social networks!

    Rispondi

Lascia un commento

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