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.423 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

Rispondi a Pkv games Terpercaya Annulla risposta

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