Ackermann Function A(n,x,y) Examples

Ackermann  Function is an extreme example of Recurrence Relations and
Recursive Functions.

The Ackermann function was discovered and studied by Wilhelm Ackermann (1896–1962) in 1928. Ackermann worked as a high-school teacher from 1927 to 1961 but was also a student of the great mathematician David Hilbert in Göttingen and, from 1953, served as an honorary professor in the university there. Together with Hilbert he published the first modern textbook on mathematical logic.

The Ackermann function can be defined as follows:
     A(0, n) = n + 1 for n = 0 
     A(m, 0) = A(m - 1, 1) for m = 1 
     A(m, n) = A(m - 1, A(m, n - 1)) for m, n = 1


Two positive integers, m and n, are the input and A(m, n) is the output in the form of another positive integer. The function can be programmed easily in just a few lines of code. The problem isn't the complexity of the function but the awesome rate at which it grows. For example, the innocuous-looking A(4,2) already has 19,729 digits!


Definition of Ackermann's Function A(n,x,y):

• A(0,x,y) = x + 1
• A(n,x,0) = x     if     n = 1
• A(n,x,0) = 0     if     n = 2
• A(n,x,0) = 1     if     n = 3
• A(n,x,0) = 2     if     n >=4
• A(n,x,y) = A(n-1,A(n,x,y-1),x)     if     n > 1 and y > 0

Recursive C++ function that calculates values for Ackermann's Function:

int Ackermann(int N, int X, int Y)

{

int K, L;

if (N == 0) return X + 1;

else if ((N > 0) && (Y == 0))

{

if (N == 1) return X;

else if (N == 2) return 0;

else if (N == 3) return 1;

else if (N >= 4) return 2;

else { cout << "Error 1: " << N << ", " << X

<< ", " << Y;

exit(1);

}

}

else if ((N > 0) && (Y > 0))

{ K = Ackermann(N, X, Y - 1);

return Ackermann(N - 1, K, X);

}

else {

cout << "Error 2: " << N << ", " << X << ", " << Y;

exit(1);

}

}