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.

47.849 thoughts on “Mastering the Ackermann Function

  1. I’m amazed, I must say. Seldom do I encounter
    a blog that’s equally educative and entertaining, and without a doubt, you’ve hit the
    nail on the head. The issue is something which too few men and women are speaking intelligently
    about. I am very happy that I came across this in my hunt for something regarding this.

  2. Hi great blog! Does running a blog such as this take a lot of work?
    I have virtually no expertise in coding but I had been hoping to start my own blog soon. Anyhow, if you have any suggestions or tips for new
    blog owners please share. I understand this is off topic however I
    simply needed to ask. Many thanks!

  3. Thanks for any other informative site. The place else could I get
    that type of info written in such an ideal means? I have a mission that I am simply now
    working on, and I have been on the glance out for such information.

  4. Everything published made a lot of sense. But, think about this, suppose you added
    a little content? I ain’t suggesting your information is
    not solid, however suppose you added a title that makes people
    want more? I mean Mastering the Ackermann Function – marzapower is a little boring.
    You ought to glance at Yahoo’s home page and see how they create news headlines to get
    people to open the links. You might add a related video or a related picture or two to
    grab readers interested about everything’ve written. Just
    my opinion, it might bring your blog a little livelier.

  5. My spouse and I absolutely love your blog and find
    a lot of your post’s to be what precisely I’m looking for.
    can you offer guest writers to write content in your case?
    I wouldn’t mind composing a post or elaborating on a few of the
    subjects you write regarding here. Again, awesome weblog!

  6. I used to be recommended this blog by way of my cousin. I am now not positive whether this post is
    written by way of him as nobody else recognize such special about
    my trouble. You are incredible! Thank you!

  7. Hello, I do believe your blog might be having browser compatibility issues.
    When I take a look at your web site in Safari, it looks fine however, if
    opening in Internet Explorer, it has some overlapping issues.
    I just wanted to provide you with a quick heads up! Besides
    that, fantastic website!

    My web-site: DevaTrim

  8. Gian hàng hội chợ là vị trí tập trung của các thương hiệu,
    doanh nghiệp, doanh nghiệp muốn truyền bá vật phẩm, vươn xa tiếng tăm tới người tiêu phí nhiều hơn. Tại đó khách tham dự
    sẽ có thể tân mắt chiêm ngưỡng, hoặc dùng thử
    item để đánh giá chất lượng. Chính bởi thế việc hút khách tham
    quan gian hàng của bạn thì gian hàng đó
    phải thật sự tuyệt vời, đã mắt, có kiến tạo độc đáo cùng cách
    bố trí item tạo sự thích mắt cho khách hàng.

    thi-cong-gian-hang-hoi-cho

    gian hàng triển lãm, xây đắp gian hàng triển lãm, xây đắp gian hàng, gian hàng hội chợ đẹp,
    thi công gian hàng hội chợ, xây đắp gian hàng hội chợ

    kiến tạo kiến thiết gian hàng hội chợ triển lãm bây
    chừ là điều rất cần thiết, cực kì quan trọng.
    bởi vì hiện thời trên thực tại nó đang rất
    được tầm thường. Khi khách đến tham quan gian hàng triển lãm điều trước tiên người ta chú ý đó
    chính là việc quan sát xe gian hàng triển lãm nào là đẹp nhất và tới xem nó.

    Giữa hàng ngàn gian hàng san sát nhau trong khu triển lãm đó thì làm
    thế nào để khách tham quan có thể tìm đến gian hàng của bạn? Đó là câu hỏi khá
    nhiều công ty, công ty ân cần. Việc khách hàng ghé
    qua và dừng chân lại tại gian hàng của bạn phổ biến chỉ trong khoảnh khắc đầu tiên khi nhìn thấy
    gian hàng của bạn.

    Nếu gian hàng triển lãm của người chơi có tính
    cách quãng, giàu sang, đẹp mắt, thì
    điều này đích thực gây ấn tượng, để lại dấu ấn trong lòng khách hàng tham quan triển lãm.

    Đây cũng là thời cơ cho cho đơn vị, đơn vị
    của người chơi quảng cáo, giới thiệu, khai triển vật
    phẩm đến khách hàng tiềm năng một cách hiệu quả.
    Để làm được như vậy thì điều trước tiên là bạn cần phải tìm tới đúng doanh nghiệp xây dựng
    xây đắp gian hàng hội chợ.

    lưu ý khi thiết kế gian hàng hội chợ
    Điều đầu tiên bạn niềm nở tới là cách xây cất
    gian hàng hội chợ thật lạ mắt,
    bắt mắt, tinh tế, không gian bên trong gian hàng tiện lợi
    cho việc bố trí, trưng bày vật phẩm cũng như có nơi để khách hàng tham quan.
    Thường thì việc kiến tạo gian hàng
    sẽ có 2 -3 mặt trống để dễ dãi cho việc quan sát của khách tham quan từ
    mọi phía, chứ nếu mặc cả 4 mặt đều trống thì gian hàng sẽ bị trơ, khách hàng thấy là đi luôn không cần biết
    bên trong gian hàng có những gì. Một gian hàng nếu
    nhưng mà chỉ có một mặt tiền trống thì họ
    cũng chỉ có thể nhìn từ bên ngoài vào, điều đó cũng làm họ thấy chán nản khi xẹp qua.

    Việc trưng bày, cách sắp xếp cống phẩm của doanh nghiệp, doanh nghiệp cũng là một
    yếu tố cần thiết chẳng thể bỏ lỡ. Phần nổi bật bên trong gian hàng hội chợ
    đó chính là cách sắp xếp sản phẩm có được nổi trội
    để thú vị sự vồ cập của khách tham quan hay không.
    Có nhiều tổ chức muốn giới thiệu cống phẩm của mình một cách độc đáo
    bằng việc làm mô hình vật phẩm lơn nhằm hút khách tham quan. mà điều này chỉ đúng, phục vụ được với một số
    gian hàng có item đặc biệt chứ không phải vật phẩm nào cũng làm mô hình lơn được.

    Dường như việc sắp xếp cống phẩm dễ ợt cho khách
    hàng có thể sờ, sử dụng thử cống phẩm, cầm trên tay
    tờ giới thiệu item đơn vị với những thông báo chi tiết hữu
    ích cũng là nhân tố được đon đả.

    Với chúng tôi, tổ chức lăng xê Á Âu có đội ngũ
    thi công gian hàng hội chợ lâu năm, chuyên nghiệp cùng chuyên gia kiến tạo gian hàng
    đầy sáng tạo, có nhiều năm kinh nghiệm về gian hàng bảo đảm sẽ đem
    tới cho bạn gian hàng mang tính chuyên nghiệp,
    đẹp mắt. Bên cạnh đó chúng tôi sẽ tư vấn xây cất miễn cho người chơi khi liên can với chúng tôi,
    chắc chắn bạn sẽ phải chấp nhận về phương thức làm việc kiến thiết gian hàng triển lãm
    của chúng tôi. bảo đảm gian hàng sẽ đem tới hiệu quả cao nhất cho công ty, đơn vị của bạn.

    Với chúng tôi việc đáp ứng khách hàng là nụ
    cười, sự hân hạnh và sự chấp nhận, niềm tin của khách hàng chính là động lực, là
    nguồn nhựa sống cho doanh nghiệp ngày một cố gắng phát triển, là tiêu
    chí để chúng tôi tiến đến và phát triển.

  9. I was recommended this blog by way of my cousin. I’m not positive whether or not this post is written by means of him as no one else recognise such precise about my trouble. You are incredible! Thanks!|

  10. What i do not realize is in truth how you
    are now not really much more smartly-liked than you may be right now.
    You’re so intelligent. You know therefore considerably with
    regards to this matter, produced me personally consider it from
    a lot of varied angles. Its like women and men are not fascinated unless it is one thing to do with Woman gaga!
    Your personal stuffs outstanding. At all times take care of it up!

  11. Excellent blog! Do you have any suggestions for aspiring writers?
    I’m hoping to start my own website soon but I’m
    a little lost on everything. Would you suggest starting with
    a free platform like WordPress or go for a paid option? There are so many options out there
    that I’m completely confused .. Any recommendations?

    Bless you!

  12. Hey, I think your website might be having browser compatibility issues.
    When I look at your blog in Opera, it looks fine
    but when opening in Internet Explorer, it has some overlapping.
    Ijust wanted to give you a qquick heads up! Other then that,
    fantastic blog!
    site

  13. My brother suggested I might like this website.
    He was totally right. This post actually made my day.
    You cann’t imagine simply how much time I had spent for this
    info! Thanks!

  14. Greetings! Quick question that’s entirely off topic.
    Do you know how to make your site mobile friendly?
    My web site looks weird when browsing from my iphone4.
    I’m trying to find a template or plugin that
    might be able to resolve this problem. If you have any recommendations,
    please share. Appreciate it!

  15. Good post. I learn something totally new and challenging on websites I stumbleupon everyday.
    It will always be interesting to read through articles from other writers and use a little something from their
    web sites.

  16. Today, I went to the beachfront with my children. I found a sea shell and gave it to my 4 year old daughter and said “You can hear the ocean if you put this to your ear.” She placed the shell to her ear
    and screamed. There was a hermit crab inside and it pinched her ear.
    She never wants to go back! LoL I know this is totally off topic but I had to
    tell someone!

  17. of course like your website but you need 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 surely come again again.

  18. wonderful post, very informative. I wonder why the other experts of this sector
    do not notice this. You should proceed your writing.
    I am sure, you have a great readers’ base already!

Lascia un commento

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