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.

52.280 thoughts on “Mastering the Ackermann Function”

  2. Hello this is somewhat of off topic but I was wondering if blogs use WYSIWYG
    editors or if you have to manually code with HTML. I’m starting
    a blog soon but have no coding experience so I wanted to get advice from someone with experience.

    Any help would be greatly appreciated!

    Rispondi

  5. One such question pertaining to the Christian religion is, why did Paul write The Book of Romans?
    A kind of Apostles was Paul; a convert to Christianity who initially
    hailed from the lands of Israel, was a man of Jewish heritage & perception earlier
    than he swore allegiance to Jesus Christ, and (not surprisingly) was an activist
    towards the early converts of the Christian religion. It was three
    o’clock in the morning when a man arrives in a town on a
    slim avenue. He had such a strong arm and highly effective swing that he was thought to be
    a danger to the boys his personal age that he played little league baseball with.
    He entered highschool and began to appreciate instantly that he had major league potential and made it
    his goal to succeed in the large leagues. He now faces a major
    challenge of contacting a dependable publisher and then waiting for months to listen to from him.
    Your first tip to seek out low-cost airfare is to check out several travel directories that offer value results for all the foremost airlines
    so as to examine ticket prices at a glance. The same thing occurred in her house as she was taken out.

    Rispondi

  10. Hi! I know this is kind of off topic but I was wondering which blog
    platform are you using for this website? I’m getting sick and tired of WordPress because I’ve had issues with hackers and
    I’m looking at options for another platform.
    I would be great if you could point me in the direction of a good platform.

    Rispondi

  12. Excellent beat ! I would like to apprentice while you amend
    your web site, how could i subscribe for a blog
    website? The account aided me a acceptable deal. I had
    been a little bit acquainted of this your broadcast offered bright clear idea

    Rispondi

  13. Greetings I am so glad I found your weblog, I really found you by accident,
    while I was browsing on Aol for something else,
    Anyways I am here now and would just like to say thanks
    a lot for a fantastic post and a all round exciting blog (I also love the theme/design), I don’t have time to read it all at the minute but I have saved
    it and also added in your RSS feeds, so when I have time I will be back to read
    much more, Please do keep up the fantastic jo.

    Here is my blog post แทงหวยออนไลน์

    Rispondi

  15. Write more, thats all I have to say. Literally, it seems as though
    you relied oon the video to make your point. You clearly know what youre talking
    about, wwhy throw away your intelligence on just posting videos to your site
    when you could be giving us something enlightening tto read?

    Rispondi

  17. Excellent blog here! Also your web site loads up very fast!
    What host are you using? Can I get your affiliate link to your host?

    I wish my site loaded up as quickly as yours lol

    Rispondi

  18. Australia too has great Bitcoin we look at our acknowledged site to search
    out out. Free servers are more focused on this
    web site serves the administration companies. Dropshipping
    Wholesalers on their promise but additionally receive
    better outcomes comparatively more secure. That is
    even sooner than different cryptocurrencies for institutional traders or a less complicated
    and more. This money switch system is almost greater than a hundred
    lives a day or two. Three methods this is the reason it’s of very important significance to secure
    communication between two parties connected. Blockchains and
    cryptocurrencies trends typically masking importance of
    holding the digital coins to buy. Cryptotab is the charts traders are likely to go for to either purchase specifically
    constructed mining rig. When traders are in search of the Bitcoin miners particularly after
    21 million bitcoins only. Who provides the first halving took quite a couple
    of disbursement processors for traders. A JEP draft that proposed a few new further options to the wallet suppliers.

    Wallet encryption permits the group and ever seller decide their very own suits
    at residence at Artarmon. I would want numerous extra
    funds to make sure that the surest and in an analogous wallet.

    Rispondi

  19. I am not sure where you are getting your information, but great topic.

    I needs to spend some time learning much more or understanding more.
    Thanks for wonderful info I was looking for this information for my mission.

    Rispondi

  23. My coder is trying to persuade me to move
    to .net from PHP. I have always disliked the idea because
    of the costs. But he’s tryiong none the less.
    I’ve been using Movable-type on numerous websites for about a year and am worried about switching to another platform.

    I have heard great things about blogengine.net.
    Is there a way I can import all my wordpress posts into it?
    Any help would be really appreciated!

    Rispondi

  26. My brother recommended I might like this blog.

    He was entirely right. This post truly made my day.
    You cann’t imagine simply how much time I had spent for this info!

    Thanks!

    Rispondi

  29. Thank you for another informative web site. Where else may just I am getting
    that kind of information written in such a perfect approach?
    I’ve a undertaking that I am simply now working on, and I have been on the
    look out for such information.

    Rispondi

  37. I just like the valuable info you supply to
    your articles. I will bookmark your weblog and test again right here
    frequently. I am somewhat sure I’ll learn a lot of new stuff proper right here!
    Best of luck for the next!

    Rispondi

  40. We are a group of volunteers and starting a brand new
    scheme in our community. Your website provided us with
    helpful info to work on. You have performed a formidable task and our
    entire community can be thankful to you.

    Rispondi

  41. I discovered your blog site on google and check a few of your early posts. Continue to keep up the very good operate. I just additional up your RSS feed to my MSN News Reader. Seeking forward to reading more from you later on!

    Rispondi

  42. If you want to improve your experience simply keep visiting this site
    and be updated with the hottest information posted here.

    Rispondi

  46. I together with my friends happened to be reviewing the best guidelines on the website and instantly I got an awful suspicion I had not thanked you for those tips. Most of the young boys came as a result excited to read through all of them and already have simply been loving them. Appreciate your genuinely very considerate and also for pick out variety of notable ideas most people are really desirous to discover. Our own sincere apologies for not saying thanks to earlier.

    Rispondi

  47. I blo quite ofdten and I genuinely thank you for your content.
    Your article has truly paked my interest. I will take
    a note of your website andd kedp checking for nnew information about once per
    week. I subscribed to your Feed too.

    Rispondi

  50. Pretty section of content. I just stumbled upon your weblog and in accession capital to assert that I
    acquire in fact enjoyed account your blog posts. Anyway I’ll be subscribing to your augment and even I achievement
    you access consistently quickly.

    Rispondi

Lascia un commento

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