What is Ackermann Function?

The Wilhelm Ackermann-inspired Ackermann function is one of the simplest and earliest examples of a complete computable function that is not basic recursive in computability theory. Although the Ackermann function demonstrates that not all total computable functions are primitive recursive, all primitive recursive functions are total and computable. The "Ackermann function" today refers to any of the many variations of the original function that were created after Ackermann published his function (which had three nonnegative integer arguments). Carry on reading to understand more about this.

Definition of Ackerman Function

As a result of several authors modifying Ackermann's function, which had three nonnegative integer arguments when it was first published, "the Ackermann function" nowadays might refer to any of the many different iterations of the original function. The two-argument Ackermann-Péter function, one popular variant, is defined as follows for nonnegative integers m and n:

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

Let's use a problem to clarify the definition.

 Ackermanfun(1, 2)

Solution:

1. The given issue is ACKERMANFUN (1, 2)
2. In this case, m = 1 and n = 2, hence m > 0 and n > 0
3. Applying the Ackermann function's third condition, ACKERMANFUN(1, 2) = ACKERMANFUN(0, ACKERMANFUN(1, 1)), results. ———- (1)
4. Now let's use the third condition of the Ackermann function, ACKERMANFUN(1, 1) = ACKERMANFUN(0, ACKERMANFUN(1, 0))———- (2)
5. Applying the second criterion of the Ackermann function, ACKERMANFUN(1, 0) = ACKERMANFUN (0, 1) ———- (3)
6. Applying the first condition of the Ackermann function, ACKERMANFUN(0, 1) = 1 + 1 = 2
7. Add this value to equation 3 now.
8. Hence ACKERMANFUN(1, 0) = 2
9. After that, enter this value into equation 2: ACKERMANFUN(1, 1) = ACKERMANFUN(0, 2) ———- (4)
10.  Let's now use the first condition of the Ackermann function, which is ACKERMANFUN(0, 2) = 2 + 1 = 3
11.  Add this value to equation 4 now, ACKERMANFUN(1,1)=3
12.  After that, enter this value into equation 1: ACKERMANFUN(1, 2) = ACKERMANFUN(0, 3) ———- (5)
13.  Applying the first condition of the Ackermann function, ACKERMANFUN(0, 3) = 3 + 1 = 4
14.  Add this value to equation 5 now.
15.  So, ACKERMANFUN(1, 2) = 4.

Let’s understand the above idea with implementation of codes.

Example 1:

// C++ program to illustrate Ackermann function
#include <iostream>
using namespace std;


int ackermanfun(int m, int n)
{
	if (m == 0){
		return n + 1;
	}
	else if((m > 0) && (n == 0)){
		return ackermanfun(m - 1, 1);
	}
	else if((m > 0) && (n > 0)){
		return ackermanfun(m - 1, ackermanfun(m, n - 1));
	}
}


// Driver code
int main()
{
	int VALUE;
	VALUE = ackermanfun(1, 2);
	cout << VALUE << endl;
	return 0;
}

Output:

Example 2:

// C program to illustrate Ackermann function
#include <stdio.h>
int ackermanfun(int m, int n)
{
	if (m == 0){
		return n+1;
	}
	else if((m > 0) && (n == 0)){
		return ackermanfun(m-1, 1);
	}
	else if((m > 0) && (n > 0)){
		return ackermanfun(m-1, ackermanfun(m, n-1));
	}
}


int main(){
	int VALUE;
	VALUE = ackermanfun(1, 2);
	printf("%d", VALUE);
	return 0;
}

Output:

Example 3:

// Java program to illustrate Ackermann function
class bn
{
	static int ackermanfun(int m, int n)
	{
		if (m == 0)
		{
			return n + 1;
		}
		else if((m > 0) && (n == 0))
		{
			return ackermanfun(m - 1, 1);
		}
		else if((m > 0) && (n > 0))
		{
			return ackermanfun(m - 1, ackermanfun(m, n - 1));
		}else
		return n + 1;
	}
	public static void main(String args[])
	{
		System.out.println(ackermanfun(1, 2));
	}
}

Output:

Example 4:

// C# program to illustrate Ackermann function
using System;
class bn
{
	static int ackermanfun(int m, int n)
	{
		if (m == 0)
		{
			return n + 1;
		}
		else if((m > 0) && (n == 0))
		{
			return ackermanfun(m - 1, 1);
		}
		else if((m > 0) && (n > 0))
		{
			return ackermanfun(m - 1, ackermanfun(m, n - 1));
		}else
		return n + 1;
	}
	public static void Main()
	{
		
		Console.WriteLine(ackermanfun(1, 2));
	}
}

Output:

Example 5:

# Python program to illustrate Ackermann function
def A(m, n, s ="% s"):
	print(s % ("A(% d, % d)" % (m, n)))
	if m == 0:
		return n + 1
	if n == 0:
		return A(m - 1, 1, s)
	n2 = A(m, n - 1, s % ("A(% d, %% s)" % (m - 1)))
	return A(m - 1, n2, s)


print(A(1, 2))

Output: