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