Ackermann Function

Posted by Unknown On Wednesday, August 11, 2010 2 comments

/*******************************************************************************

--> The Ackermann Function is a very important function originally suggested by Wilhelm Ackermann
in 1928 and later modified by Rozsa Peter.

Wilhelm Ackermann

If m = 0 then A(m,n) = n + 1

If m != 0 but n = 0 then A(m,n) = A(m - 1,1)

If m != 0 and n != 0 then A(m,n) = A(m - 1, A(m,n - 1))

This function is interesting because of its remarkably rapid growth.It grows so fast that it is guaranteed not to have a representation by a formula that uses arithmetic operations such as addition, multiplication, and exponentiation. To illustrate the rate of growth of the Ackermann function, we need only show that with a stack of n 2s in the exponent; A(4,1) = 2^(2 ^ 16) - 3 = (2 ^ 65536) - 3, which exceeds even the number of atoms in the universe (which is 10^80 according to current theories).

APPLICATION : Ackermann Function

CODED BY : Ankit Pokhrel

COMPILED ON : Borland C++ Ver 5.02

DATE : 2010 - August - 10

*******************************************************************************/

#include "iostream.h"
#include "conio.h"

unsigned long count = 0;
long Ackermann(int m,int n)

Drawing of the analytic extention of the Acker...

Analytical Extension of Ackermann Function

{
count++;
if(m == 0)
  return (n + 1);

else if(m != 0 && n == 0)
return Ackermann(m - 1,1);

else
  return Ackermann(m - 1, Ackermann(m,n - 1));
}

long main()
{
int m,n;
cout << "Ackermann(M,N)\nEnter values for M and N : ";
cin >> m >> n;
if(m < 0 || n < 0)
  {
   cout << "\nEnter Values Greater than Zero";
   getch();
   return 0;
  }

long result = Ackermann(m,n);
cout << "\nAckermann(" << m << ',' << n << ") : " << result;
cout << "\nSteps : " << count;
getch();
return 0;
}