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.

56.452 thoughts on “Mastering the Ackermann Function”

  1. Wonderful goods from you, man. I’ve understand your stuff previous to
    and you are just too great. I really like what you’ve acquired here, certainly like what you are stating andd tthe way iin which you say
    it. You make it entertaining and you still care for
    to keep it smart. I can’t wait to read much more from you.
    This is really a great website.

    Rispondi

  2. Today, I went to the beach with my kids. 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 put 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 completely off topic but I had to tell
    someone!

    Rispondi

  3. Pretty component to content. I just stumbled upon your website and
    in accession capital to say that I acquire in fact enjoyed account your weblog posts.

    Anyway I will be subscribing to your feeds and even I achievement you get right of entry to constantly quickly.

    Rispondi

  6. What i don’t understood is if truth be told how you are now not really much
    more neatly-favored than you may be right now. You’re very intelligent.

    You realize therefore considerably in the case of this matter,
    produced me individually imagine it from numerous various angles.
    Its like women and men are not fascinated unless it’s one thing to do with Lady gaga!
    Your personal stuffs nice. Always deal with it up!

    Rispondi

  7. I’m amazed, I have to admit. Seldom do I come across a blog that’s equally educative and
    engaging, and without a doubt, you’ve hit the nail on the head.
    The issue is something too few people are speaking intelligently
    about. I’m very happy I came across this in my search for something concerning this.

    Rispondi

  9. Hi there I am so glad I found your web site, I really found you by error, while I was
    researching on Digg for something else, Anyways I am here
    now and would just like to say many thanks for a tremendous post and a all round thrilling blog (I
    also love the theme/design), I don’t have time to go through it all at the
    minute but I have bookmarked 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 great
    work.

    Rispondi

  10. Pretty section of content. I just stumbled upon your blog and in accession capital to assert that I get actually enjoyed account your
    blog posts. Any way I will be subscribing to your augment and even I achievement you
    access consistently rapidly.

    Rispondi

  14. I have recently started a web site, the info you offer on this site has helped me greatly. Thank you for all of your time & work. “The very ink with which history is written is merely fluid prejudice.” by Mark Twain.

    Rispondi

  17. Write more, thats all I have to say. Literally, it seems
    as though you relied on the video to make your point. You obviously 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

  18. This design is steller! You certainly 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!) Excellent job. I really loved what you had to say,
    and more than that, how you presented it. Too cool!

    Rispondi

  19. I must show some appreciation to this writer for bailing me out of such a circumstance. Because of scouting through the search engines and coming across tips which were not pleasant, I thought my entire life was over. Being alive without the solutions to the difficulties you have sorted out through your posting is a critical case, as well as the kind that could have adversely damaged my entire career if I hadn’t encountered your site. Your own training and kindness in taking care of every part was excellent. I’m not sure what I would’ve done if I had not encountered such a subject like this. I can at this point look forward to my future. Thanks very much for this specialized and effective guide. I will not hesitate to suggest the blog to anybody who needs guidance on this subject.

    Rispondi

  22. Thanks on your marvelous posting! I certainly enjoyed
    reading it, you will be a great author.I will make sure to bookmark your blog and may come back sometime soon. I want to encourage you to ultimately continue your
    great posts, have a nice afternoon!

    Rispondi

  23. My partner and I stumbled over here by a different web address and thought I might check things out.
    I like what I see so now i’m following you.
    Look forward to going over your web page again.

    Rispondi

  24. giả dụ bạn đang cần tiền gấp thì các nhà cung cấp
    choo vay tiền nhanh online chính là chọn lựa số một ccho bạn. Trên thị phần hiện tại với
    đông đảo đơn vị cung ứng nhà sản xuất vay tiền nhanh online
    được Đánh giá cao. không cạnh tranh, đa dạng giấy má như các kênh nhà băng, đây là cách thức những tổ chức tài chính lách
    qua khe cửa để tăng trưởng rất nhah những năm mới đây.

    So với nhà sản xuất cầm đồ hay vay tiền nhà băng thì nhà sản xuất vốn đầu
    tư, vay vốn online được lựa chọn vì giấy tờ
    đơn giản, chỉ cần CMND và thời kì giải ngân khôn cùng chóng vánh.
    Nhớ lại khi đi vay tiền nhà băng, bạnsẽ phải làm hầu hết giấy tờ xin vay, giấy tờ lằng nhằng.
    Và thêm nữa, ngân hàng chắc chắn sẽ bắt buộc bạn cung ứng một dòng
    tài sản để đảm bảo khỏan vay. với trường
    hợp được trả lương qua thẻ ngân hàng, bạn với thể được tiếp cận hình thức vay vốn tín chấp nhưng hạn mức rất phải chăng.

    tuy nhiên rõ ràng là các hình thức này không liên quan hoàn toàn được nhu cầu của
    phần đông mọi người. không hề ai cũng với tài sản để thế chấp nhà băng,
    không hề ai cũng được nhận lương chuyển khoản. Mà toàn bộ người cần vay tiền nhanh để
    giải quyết mau chóng những vấn đề nhu yếu trong cuộc sống của họ.
    những lý do vậy dẫn đến việc hồ hết đơn vị
    nguồn vốn khai triển các dịch vụ vay tiền nhanh.

    Trong thị trấn hội khoa học thông tin và internet vững mạnh như hiện tại, thì đây là hình thức vay tiền hiệu quả.
    có phố hội hiện đại thì đây rõ ràng là bước tiến lớn, đáp ứng trông
    chờvà nhu cầu của người dân. Hiểu
    đơn thuần nhất thì vay tiền online là hình thức
    cho vay tín chấp được luật pháp cho phép.
    Hình thức vay tín chấp này được những nhà băng
    áp dùng trong khoảng lâu.

    Also visit my webpage: vay tien nhanh|vay tiền nhanh|vay tiền nóng|vay tien Nong|vay tiền online|vay tien online|vay tien nhanh ha noi|vay tien nhanh sai gon|vay tien nhanh tphcm|vay tiền nhanh tphcm|vay tiền nhanh hà nội|vay tiền nhanh sài gòn|vay tiền nhanh đà nẵng|vay tien nhanh da nang|vay tien nhanh hai phong|vay tiềN nhanh hải phòng|vay tiền online hà nội|vay tien online ha noi|vay tien online tphcm|vay tiền online tphcm|vay tiền bát họ|vay tien bat ho|vay tiền nóng hà nội|vay tien nong ha noi|vay tien nong tphcm|vay tiền nóng tphcm|vay tiền nhanh bình dường|vay tien nhanh binh duong|vay tin chap|vay tín chấp|vay tien cmnd|vay tiền cmnd|vay tien cccd|vay tiền cccd

    Rispondi

  27. An intriguing discussion is worth comment. I believe that you need to write more on this
    issue, it might not be a taboo subject but usually people
    do not talk about such subjects. To the next! Best wishes!!

    Rispondi

  45. Ԝe are a group off voⅼunteers and starting a nnew scheme іn our community.

    Your website provided us with valuable informаtion to work on. You
    have done an impressive joЬ annd our whоe community ᴡilⅼ bbe thankful to you.

    Here іs my page; domino online

    Rispondi

  46. Howdy! I could have sworn I’ve visited this site before but after browsing through many of the articles I realized it’s new to me.
    Anyhow, I’m definitely delighted I discovered it
    and I’ll be book-marking it and checking back often!

    Rispondi

  49. Hmm it seems like your website ate my first comment (it was
    super long) so I guess I’ll just sum it up what I wrote and say,
    I’m thoroughly enjoying your blog. I too am
    an aspiring blog writer but I’m still new to everything.
    Do you have any points for newbie blog writers?
    I’d definitely appreciate it.

    Rispondi

Rispondi a kunjungi website kami Annulla risposta

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