Mastering the Ackermann Function – Part 2

Posted on by marzapower

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

1.792 thoughts on “Mastering the Ackermann Function – Part 2”

  2. I intended to draft you a bit of remark to thank you very much again for these incredible methods you’ve discussed in this article. It has been certainly remarkably generous of people like you to present freely exactly what a number of us could have distributed for an ebook to help with making some bucks for themselves, and in particular given that you could have tried it if you ever desired. These thoughts in addition worked as a easy way to realize that other people have similar interest much like mine to know many more with regard to this condition. I’m certain there are numerous more enjoyable times up front for people who take a look at your site.

    Rispondi

  5. You are so interesting! I don’t believe I’ve truly read a single thing like that before. So nice to discover someone with unique thoughts on this issue. Really.. thank you for starting this up. This site is one thing that is needed on the internet, someone with some originality!

    Rispondi
  18. Pingback: Videocam Models wanted

  22. I’m not sure where you’re getting your information, but great topic. I needs to spend some time learning more or understanding more. Thanks for fantastic information I was looking for this information for my mission.

    Rispondi

  24. We are a group of volunteers and starting a new scheme in our community. Your web site provided us with valuable information to work on. You’ve done an impressive job and our entire community will be grateful to you.

    Rispondi

  26. Hi! I could have sworn Iíve been to this website before but after looking at a few of the posts I realized itís new to me. Anyhow, Iím certainly happy I discovered it and Iíll be bookmarking it and checking back regularly!

    Rispondi

  29. I am also writing to let you understand what a outstanding encounter my friend’s child experienced browsing your web site. She discovered too many details, not to mention what it is like to possess a great coaching heart to get the mediocre ones easily fully understand some tortuous things. You actually did more than our expected results. I appreciate you for coming up with such invaluable, trusted, educational and also easy guidance on this topic to Jane.

    Rispondi

  33. Oh my goodness! Amazing article dude! Many thanks, However I am going through difficulties with your RSS. I don’t understand why I can’t join it. Is there anybody else getting identical RSS issues? Anyone who knows the solution will you kindly respond? Thanx!!

    Rispondi
  40. Pingback: comentarios clinicas dh

Lascia un commento

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