Sage should have a special function -- Ackermann Function

[vaibhavkarve]

The Ackermann function is important to theoretical CS folks and is a very classic function.

• https://en.wikipedia.org/wiki/Ackermann_function

Sage can have this function defined.
Possible suggestions/features could look like:

1. There are many variants of the function but it seems pretty natural to include the two-argument Ackermann–Péter variant (this is also detailed in the wikipedia link).

2. Sage can include known values of the Ackermann function for (m,n) pairs eg: $Ackermann(4,2) = 2²⁶⁵⁵³⁶ − 3$ etc.

3. Its Taylor series expansion is also known. (I don't have a link for this. But I believe Wolfram Alpha displays it.)

Here is another link to some Ackermann function values:

• http://www-users.cs.york.ac.uk/~susan/cyc/a/ackermnn.htm

CC: @slel

Component: coding theory

Keywords: special function, recursive function

Issue created by migration from https://trac.sagemath.org/ticket/25175

[slel]

Description changed:

--- 
+++ 
@@ -1,11 +1,16 @@
-The Ackermann function is important to theoretical CS folks and is a very classic function. [https://en.wikipedia.org/wiki/Ackermann_function](https://en.wikipedia.org/wiki/Ackermann_function)
+The Ackermann function is important to theoretical CS folks and is a very classic function. 
+
+- [https://en.wikipedia.org/wiki/Ackermann_function](https://en.wikipedia.org/wiki/Ackermann_function)
+
 Sage can have this function defined.
 Possible suggestions/features could look like:
 
 1. There are many variants of the function but it seems pretty natural to include the two-argument Ackermann–Péter variant (this is also detailed in the wikipedia link).
 
-2. Sage can include known values of the Ackermann function for (m,n) pairs eg: $Ackermann(4,2) = 2^265536 − 3$ etc.
+2. Sage can include known values of the Ackermann function for (m,n) pairs eg: $Ackermann(4,2) = 2<sup>265536</sup> − 3$ etc.
 
 3. Its Taylor series expansion is also known. (I don't have a link for this. But I believe Wolfram Alpha displays it.)
 
-Here is another link to some Ackermann function values: [http://www-users.cs.york.ac.uk/~susan/cyc/a/ackermnn.htm](http://www-users.cs.york.ac.uk/~susan/cyc/a/ackermnn.htm)
+Here is another link to some Ackermann function values:
+
+- [http://www-users.cs.york.ac.uk/~susan/cyc/a/ackermnn.htm](http://www-users.cs.york.ac.uk/~susan/cyc/a/ackermnn.htm)

[jdemeyer]

Replying to @vaibhavkarve:

2. Sage can include known values of the Ackermann function for (m,n) pairs eg: $Ackermann(4,2) = 2²⁶⁵⁵³⁶ − 3$ etc.

More generally, since integers in Sage are limited by 2<sup>(2</sup>67), we could implement this by a simple lookup:

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

2. A(1,n) = n + 2

3. A(2,n) = 2n + 3

4. A(3,n) = 2ⁿ⁺³ - 3

5. A(4,0) = 13

6. A(4,1) = 65533

7. A(4,2) = 2⁶⁵⁵³⁶ − 3

8. A(5,0) = 65533

9. raise OverflowError in all other cases.