Mastering the Ackermann Function – Part 2

In one of my latest posts I reviewed the Ackermann function. We left with some unsolved problems about efficiency and computability of the function itself. Throughout this post I’ll give another point of view for the Ackermann function, and something magic wil come out …

Another form

The function A(x, y) is defined for every real pair (x, y). If we restrict the domain of x and y to the Integer set, we get a different image for the function. That is:

  1. A(0, y) = y + 1
  2. A(1, y) = y + 2
  3. A(2, y) = 2y + 3
  4. A(3, y) = 2^(y+3) – 3
  5. A(4, y) = 2^2^2^ … ^2 – 3
  6. A(5, y) = ?

As we can see, the form of A(x, y) becomes more and more difficult as x grows. Eg. to compute A(4, y) one has to compute the exponentiation of 2 by 2 for y+3 times. If you look carefully, though, you can see that the Ackermann function underlies an interesting pattern. It will be more clear if we chose a little different form of A(x, y).

Buck’s function

Buck’s function has the same recursive pattern of Ackermann’s function, but with different boundary values. That is:

$$F(x, y) = F(x-1, F(x, y-1))$$

with

$$F(0,y) = y+1 \\ F(1,0) = 2 \\ F(2,0) = 0 \\ F(x, 0) = 1, for x = 3,4,\dots$$

Well, starting from here, we have the following:

$$F(0, y) = y + 1 \\ F(1, y) = 2y \\ F(2, y) = 2^y \\ F(3, y) = 2^{2^{\dots^2}} = 2\uparrow\uparrow y$$

Now the pattern should be clear:

  1. x = 0 represents the sum
  2. x = 1 represents the repetition of the sum y times, the multiplication
  3. x = 2 represents the repetition of the multiplication y times, the exponentiation
  4. x = 3 represents the repetition of the exponentiation y times, the so called power tower

and so on. To represent in a concise form the latter case the Knoth’s up-arrow notation has been used. We can use this notation to generalize the function this way:

$$F(x, y) = 2\uparrow^{x – 1}y, \ \ \ \ \ \text{for } x \geq 2$$

Easily, we can see the Buck’s function as a succession of operators and hyper operators:

$$(+, \times, \uparrow, \uparrow\uparrow, \uparrow\uparrow\uparrow, \ldots, \uparrow^{n}, \ldots)$$

Back to algorithms

I started this “conversation” speaking about algorithmic implementation. We can now rewrite the Ackermann’s function in a different way, as expressed in the beginning of this article. Sadly, we define the new function only for x < 5:

import sys
from math import pow

def A2(x, y):
  
  if x <= 1: return x + y + 1; if x == 2: return 2 * y + 3 if x == 3: return pow(2, y + 3) if x == 4: res = 2 y += 3 while y > 1:
      res = pow(2, res)
      y -= 1
    return res - 3
  
  return 0

x = int(sys.argv[1])
y = int(sys.argv[2])

print "Result of A2(%d, %d) is %d" % (x, y, A2(x, y))

Now, the algorithm will give results till A(4, 1). As we said, A(4, 2) has about 19,000 decimal digits, since it’s equal to $$2^{65536}-3$$.

I will also give you an implementation of the Buck’s function, using a generalized implementation of the hyper operator function:

import sys
from math import pow

def F(x, y):
  if x == 0:
    return y + 1
  if x == 1:
    return 2 * y
  if x == 2:
    return pow(2, y)
  return hyper(2, x, y)


def hyper(a, n, b):
  if n == 1:
    return pow(a, b)
  if b == 0:
    return 1
  return hyper(a, b - 1, hyper(a, b, n - 1))

x = int(sys.argv[1])
y = int(sys.argv[2])

print "Result of F(%d, %d) is %d" % (x, y, F(x, y))

where hyper(a, n, b) is the simpler algorithmic implementation to $$a\uparrow^{n}b$$.

The Nightmare returns, once again

Did you notice something in the last piece of code? Isn’t the hyper(a, n, b) function similar, in its recursive form, to the Ackermann’s function?

It simply is not possible to efficiently compute A(x, y) for “large” values of x (x >= 4).

725 thoughts on “Mastering the Ackermann Function – Part 2

  1. You could certainly see your skills within the paintings you write. The arena hopes for more passionate writers like you who aren’t afraid to say how they believe. Always follow your heart.

  2. Aw, this was an exceptionally nice post. Taking a few minutes and actual effort to generate a really good article… but what can I say… I procrastinate a whole lot and never seem to get nearly anything done.

  3. My husband and i got very joyful that Raymond could conclude his homework by way of the precious recommendations he had out of the web pages. It is now and again perplexing to just find yourself releasing ideas which usually some people have been making money from. And we already know we have got you to give thanks to because of that. The main explanations you have made, the straightforward web site navigation, the friendships you can aid to foster – it’s got mostly astounding, and it’s really leading our son and us imagine that that subject is exciting, which is extraordinarily indispensable. Thanks for everything!

  4. Right here is the right blog for anybody who really wants to understand this topic. You know so much its almost hard to argue with you (not that I personally would want to…HaHa). You certainly put a new spin on a subject that has been discussed for decades. Wonderful stuff, just excellent.

  5. Hi there! I could have sworn I’ve visited this site before but after going through many of the articles I realized it’s new to me. Regardless, I’m definitely delighted I discovered it and I’ll be bookmarking it and checking back often.

  6. What’s Going down i’m new to this, I stumbled upon this I have discovered It positively helpful and it has helped me out loads. I am hoping to give a contribution & aid other users like its aided me. Great job.

  7. I do agree with all the ideas you have presented in your post. They’re really convincing and will definitely work. Still, the posts are too short for starters. Could you please extend them a little from next time? Thanks for the post.

  8. Oh my goodness! Awesome article dude! Many thanks, However I am encountering troubles with your RSS. I don’t understand why I am unable to join it. Is there anybody having similar RSS issues? Anyone who knows the answer will you kindly respond? Thanx.

  9. I just want to tell you that I am very new to weblog and truly loved your web blog. Most likely I’m going to bookmark your site . You amazingly have incredible posts. Kudos for sharing your web-site.

  10. Good – I should certainly pronounce, impressed with your site. I had no trouble navigating through all the tabs as well as related information ended up being truly simple to do to access. I recently found what I hoped for before you know it in the least. Reasonably unusual. Is likely to appreciate it for those who add forums or something, website theme . a tones way for your customer to communicate. Nice task..

  11. Thanks for the sensible critique. Me & my neighbor were just preparing to do a little research on this. We got a grab a book from our local library but I think I learned more from this post. I am very glad to see such great info being shared freely out there.

  12. I simply want to tell you that I’m very new to blogs and really enjoyed this blog site. Very likely I’m likely to bookmark your blog post . You really have beneficial articles. Thank you for sharing with us your web site.

  13. I simply want to say I am just very new to weblog and actually enjoyed your web-site. More than likely I’m going to bookmark your blog post . You definitely come with outstanding writings. Thank you for sharing with us your blog.

  14. I’m amazed, I must say. Rarely do I come across a blog that’s both educative and engaging, and without a doubt, you have hit the nail on the head. The issue is something too few folks are speaking intelligently about. I’m very happy that I stumbled across this during my hunt for something regarding this.

  15. hello!,I like your writing very much! share we keep in touch more about your post on AOL? I need an expert on this space to unravel my problem. May be that is you! Having a look ahead to peer you.

Lascia un commento

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