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.

48.838 thoughts on “Mastering the Ackermann Function”

  4. Excellent post. Keep posting such kind of info on your site.
    Im really impressed by your blog.
    Hey there, You’ve done a fantastic job. I’ll definitely digg it and in my opinion suggest to my friends.
    I am sure they will be benefited from this site.

    Rispondi

  15. My spouse and I absolutely love your blog and find nearly
    all of your post’s to be exactly what I’m looking for.
    can you offer guest writers to write content to suit your needs?
    I wouldn’t mind publishing a post or elaborating on a number of
    the subjects you write regarding here. Again, awesome weblog!

    Rispondi

  16. After checking out a number of the articles on your site,
    I truly appreciate your technique of writing a blog.
    I saved it to my bookmark website list and will be checking back in the near future.
    Take a look at my web site as well and tell me what you think.

    Rispondi

  17. Hi, Neat post. There’s an issue together with your website in web explorer, may
    test this? IE still is the marketplace leader and a
    big part of other folks will leave out your fantastic
    writing because of this problem.

    Rispondi

  20. Right here is the perfect site for anyone who hopes to find out about
    this topic. You understand so much its almost tough to argue
    with you (not that I actually will need to…HaHa). You definitely put
    a new spin on a topic that has been written about for ages.
    Great stuff, just excellent!

    Rispondi

  22. Hi! I know this is kinda off topic but I’d figured I’d ask.
    Would you be interested in trading links or maybe guest authoring a blog article or
    vice-versa? My website discusses a lot of the same
    topics as yours and I think we could greatly benefit from each other.
    If you are interested feel free to shoot me an email.
    I look forward to hearing from you! Excellent blog by the way!

    Rispondi

  24. Woah! I’m really loving the template/theme of this site.

    It’s simple, yet effective. A lot of times it’s very hard to get
    that “perfect balance” between usability and
    visual appeal. I must say you’ve done a very good job
    with this. In addition, the blog loads very quick for me on Chrome.
    Exceptional Blog!

    Rispondi

  29. Hi there! I realize this is kind of off-topic but I needed to ask.

    Does running a well-established blog like yours require a large amount of work?
    I’m brand new to operating a blog but I do write in my diary daily.
    I’d like to start a blog so I can share my experience and thoughts online.

    Please let me know if you have any recommendations or tips for new aspiring blog
    owners. Thankyou!

    Rispondi

  31. Write more, thats all I have to say. Literally, it seems as though you relied on the video to make your point.

    You definitely know what youre talking about,
    why throw away your intelligence on just posting videos to your weblog when you could be giving us something informative to read?

    Rispondi

  34. Having read this I believed it was very informative.

    I appreciate you finding the time and energy to put this article together.
    I once again find myself personally spending way
    too much time both reading and posting comments. But
    so what, it was still worthwhile!

    Rispondi

  35. First off I would like to say superb blog! I had a quick question in which I’d
    like to ask if you do not mind. I was curious to find out how you center yourself
    and clear your head prior to writing. I’ve had a
    hard time clearing my thoughts in getting my thoughts out.
    I truly do enjoy writing but it just seems like the first 10 to 15 minutes are generally lost just trying to figure out how to begin. Any suggestions or hints?
    Appreciate it!

    My blog post – Green Garden CBD Oil Review

    Rispondi

Rispondi a 강남셔츠룸 Annulla risposta

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