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.

48.811 thoughts on “Mastering the Ackermann Function

  1. I am the business manager of Eastern Ray luxury shisha pipe hire uk weddings birthdays Events (easternrayshisha.ϲo.uk),
    a hіgh-end shjsha pipe hire company. Ԝe are presently planning a large wedding celebration ϳust
    outsіԁe London аnd I am ⅼooking foг dependable DJ & Disco Hire Ӏ
    ԝas speculating іf ɑnyone аt marzapower.ϲom ccan help me.
    Doeѕ аnyone happen tο possess some nearby contacts?
    Ƭhe customer iss һappy tо employ personnel from
    anotһеr country аs quality iѕ the pivotal consideration. Money is not an issue.

    Тhank yⲟu in advance.

  2. Pretty nice post. I just stumbled upon your blog and wanted to
    say that I have truly enjoyed surfing around your blog posts.
    In any case I will be subscribing to your rss feed
    and I hope you write again very soon!

  3. Thanks for some other informative site. Where else may just I am getting that type of info written in such an ideal approach?
    I’ve a mission that I’m simply now working on, and
    I have been at the look out for such information.

  4. This design is steller! You most certainly know how to keep a reader entertained.
    Between your wit and your videos, I was almost moved to start my own blog (well, almost…HaHa!) Great job.

    I really enjoyed what you had to say, and more than that,
    how you presented it. Too cool!

  5. I oversee a vape shop web directory ɑnd ѡe have hhad a listing froom a vpe store іn the United Statеs that additionally ⲟffers for sale CBD ɡoods.
    A Calendar month ⅼater on, PayPal has written to use how to use cbd axis kief claim tһat our account hаs ƅеen restricted аnd havе requested սs to take
    away PayPal ɑѕ а ayment solution fгom our vape store submission site.

    Ԝe do not retail CBD ցoods ⅼike CBD oil. We simply provide marketing ɑnd advertijsing solutions tο CBD companies.
    I hаvе visited Holland & Barrett– tһe UK’s Leding Health Store and іf you tаke a gߋod look, you will wittness
    tat tһey offfer a rathеr wide-ranging stable of CBD gooⅾs, ρarticularly CBD oil
    and they also happen tߋ takie PayPal as a settlement solution. Іt seеms tһat
    PayPal is employing twwos sets of rules to mɑny different firms.

    Βecause ߋf thiѕ limitation, I cann no lⲟnger accept
    PayPal οn my CBD-гelated internet site. Тhis has restrained mʏ payment options and presently,
    I am greatly dependent on Cryptocurrency payments аnd straigtforward bank transfers.
    Ι hɑve checked wjth а lawyer from a Magic Circle law fiirm
    in The city oof london and thеү said that wһat PayPaal iss
    doing iss altogether illegal аnd inequtable as it shⲟuld ƅe applying ɑ systematic benchmark t᧐ all companies.
    I am yet to seek advice fгom a ԁifferent attorney from a US law firm in London tо sеe ᴡhat PayPal’s legal position is іn tthe United States.
    Foor the time beіng, I would be extremely ppreciative if anybody
    һere аt marzapower.com coսld offer me with alternative payment
    processors/merchants tһat woгk witһ CBD firms.

  6. A person essentially lend a hand to make seriously posts I’d state.
    This is the very first time I frequented your website page and so far?
    I surprised with the research you made to make this actual publish extraordinary.

    Magnificent task!

  7. Hello this is somewhat of off topic but I was wanting
    to know if blogs use WYSIWYG editors or if you have to manually code
    with HTML. I’m starting a blog soon but have no coding skills so I
    wanted to get advice from someone with experience. Any
    help would be greatly appreciated!

  8. This design is incredible! You definitely know how
    to keep a reader amused. Between your wit and your videos, I
    was almost moved to start my own blog (well, almost…HaHa!) Great job.
    I really enjoyed what you had to say, and more than that,
    how you presented it. Too cool!

    Also visit my blog post :: Manscape

  9. Howdy just wanted to give you a quick heads up. The words in your post seem to be running off the
    screen in Chrome. I’m not sure if this is a format issue
    or something to do with internet browser compatibility but I thought I’d post to let you know.
    The layout look great though! Hope you get the issue resolved soon. Cheers

  10. Hello, i think that i noticed you visited my website
    thus i came to return the desire?.I am trying to to find
    things to enhance my site!I guess its good enough to use some of your ideas!!

    Here is my web-site; Men suit

  11. Good day! This is kind of off topic but I need some advice from an established blog. Is it very hard to set up your own blog? I’m not very techincal but I can figure things out pretty fast. I’m thinking about setting up my own but I’m not sure where to begin. Do you have any ideas or suggestions? Appreciate it|

  12. Great items from you, man. I have be aware your
    stuff previous to and you’re simply extremely excellent.
    I really like what you’ve acquired right here, really like what you
    are stating and the way through which you say it. You are
    making it entertaining and you still care for to
    keep it smart. I can’t wait to learn far more from you. That is really a tremendous site.

    Also visit my website :: car hire alicante airport

  13. I was extremely pleased to discover this site.
    I want to to thank you for ones time just for this fantastic read!!
    I definitely liked every part of it and i also have you book marked to see new stuff in your web site.

  14. Hello There. I discovered your weblog the usage of msn. This is an extremely smartly
    written article. I will make sure to bookmark it and return to learn extra of your helpful information. Thanks for the post.
    I’ll certainly comeback.

    Feel free to surf to my website: Vytautas

  15. Hey there! I realize this is sort of off-topic however I needed to ask.

    Does operating a well-established website such as yours require a large amount of
    work? I am brand new to operating a blog however
    I do write in my diary every day. I’d like to start a blog so I can easily share my own experience and views online.
    Please let me know if you have any kind of recommendations or tips for brand
    new aspiring blog owners. Thankyou!

  16. My brother suggested I would possibly like this website. He was once entirely
    right. This put up truly made my day. You can not imagine simply how a lot time I had spent for
    this info! Thank you!

    Here is my blog – Sluts

  17. It’s the best time to make a few plans for the longer term and it’s time to be happy.

    I have read this put up and if I may I desire to recommend
    you few attention-grabbing issues or suggestions.
    Perhaps you could write subsequent articles referring to this article.
    I want to read more things approximately it!

  18. Simply wish to say your article is as amazing.
    The clearness for your publish is just spectacular and that i
    could think you’re knowledgeable on this subject. Well together with
    your permission let me to seize your feed to stay updated
    with forthcoming post. Thanks a million and
    please continue the rewarding work.

  19. Hi there! Someone in my Facebook group shared this site with us
    so I came to look it over. I’m definitely enjoying the information. I’m book-marking
    and will be tweeting this to my followers! Superb blog and terrific design and style.

  20. Howdy would you mind letting me know which web host you’re working with?
    I’ve loaded your blog in 3 different web browsers and I must say
    this blog loads a lot faster then most. Can you recommend a good hosting provider at a reasonable price?
    Many thanks, I appreciate it!

Lascia un commento

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