A046859 Simplified Ackermann function (main diagonal of Ackermann-Péter function).

1, 3, 7, 61

Offset: 0

Author

Don Knuth

Keywords

• nonn
• bref

Comments

The next term is 2^(2^(2^(2^16))) - 3, which is too large to display in the DATA lines.

Another version of the Ackermann numbers is the sequence 1^1, 2^^2, 3^^^3, 4^^^^4, 5^^^^^5, ..., which begins 1, 4, 3^3^3^... (where the number of 3's in the tower is 3^3^3 = 7625597484987), ... [Conway and Guy]. This grows too rapidly to have its own entry in the OEIS.

An even more rapidly growing sequence is the Conway-Guy sequence 1, 2->2, 3->3->3, 4->4->4->4, ..., which agrees with the sequence in the previous comment for n <= 3, but then the 4th term is very much larger than 4^^^^4.

From Natan Arie Consigli, Apr 10 2016: (Start)

A189896 = succ(0), 1+1, 2*2, 3^3,..., also called Ackermann numbers, is a weaker version of the above sequence.

The Ackermann functions are well-known to be simple examples of computable (implementable using a combination of while/for-loops) but not primitive recursive (implementable using only for-loops) functions.

See A054871 for the definitions of the hyperoperations (a[n]b and H_n(a,b)).

The original Ackermann function f is defined by:

{

{f(0,y,z)=y+z;

{f(1,y,0)=0;

{f(2,y,0)=1;

{f(x,y,0)=x;

{f(x,y,z)=f(x-1,y,f(x,y,z-1))

{

Here we have f(1,y,z)=y*z, f(2,y,z)=y^z.

Ackermann function variants are 3-argument functions that satisfy the recurrence relation above.

Example:

the hyperoperation function H(x,y,z) satisfies the original's recurrence relation but has the following initial values:

{

{H(0,y,z) = y+1;

{H(1,y,0) = y;

{H(2,y,0) = 0;

{H(n,y,0) = 1.

{

The family of Ackermann functions can be simplified by omitting the "y" variable of the 3-argument function by making them have two arguments.

A 2-argument Ackermann function would then be a function satisfying the recurrence relation: f(x,z)=f(x-1,f(x,z-1)).

The most popular example is Ackermann-Péter's function defined by:

{

{A(0,y) = y+1;

{A(x+1,0) = A(x,1);

{A(x+1,y+1) = A(x,A(x+1,y))

{

Here we have A(0,y-1) = y = 2[0](y-1+3)-3.

Suppose A(x-1,y-1) = 2[x-1](y-1+3)-3.

By induction on positive x:

since 2[x]2 = 4 (See A255176) we have A(x,0) = A(x-1,1) = 2[x-1]4-3 = 2[x-1]2[x-1]2-3 = 2[x-1]3-3.

By induction on positive y we can conclude that:

A(x,y) = A(x-1,A(x,y-1)) = 2[x-1](2[x](y-1+3)-3+3)-3 = 2[x-1]2[x](y-1+3)-3 = 2[x](y+3)-3.

*

If f is a 3-argument (2-argument) Ackermann function, Ack(n) = f(n,n,n) (f(n,n)) is called a simplified Ackermann function. The "Ackermann numbers" are the values of Ack(n).

Here we have a(n) = A(n,n) = 2[n](n+3)-3.

(End)

Examples

			From _Natan Arie Consigli_, Apr 10 2016: (Start)
a(0) = 2[0](0+3)-3 = 1;
a(1) = 2[1](1+3)-3 = 3;
a(2) = 2[2](2+3)-3 = 7;
a(3) = 2[3](3+3)-3 = 61;
a(4) = 2[4](4+3)-3 = 2^(2^(2^65536)) - 3.  (End)
		

References

• Conway, J. H. and Guy, R. K. The Book of Numbers. New York: Springer-Verlag, p. 60, 1996.
• G. Everest, A. van der Poorten, I. Shparlinski and T. Ward, Recurrence Sequences, Amer. Math. Soc., 2003; see esp. p. 255.
• H. Hermes, Aufzaehlbarkeit, Entscheidbarkeit, Berechenbarkeit: Einfuehrung in die Theorie der rekursiven Funktionen (3rd ed., Springer, 1978), 83-89.
• H. Hermes, ditto, 2nd ed. also available in English (Springer, 1969), ch. 13

Links

• W. Ackermann, Zum Hilbertschen Aufbau der reellen Zahlen, Math. Ann. 99 (1928), 118-133.
• D. E. Knuth and N. J. A. Sloane, Correspondence, May 1970
• Index entries for sequences related to Ackermann function

Crossrefs

Cf. A059936, A266200, A271553. (sequences involving simplified Ackermann Functions)

Cf. A001695, A014221, A143797, A264929 (sequences involving other versions of two-argument Ackermann's Function).

Cf. A054871, A189896 (sequences involving variants of the three-argument Ackermann's Function).

Cf. A126333 (a(n)=A(n,0)), A074877 (a(n)=A(3,n)).

Cf. A260002-A260006 (sequences with Sudan's function, another computable but not primitive recursive function).

Cf. A266201 (Goodstein's function, total and not primitive recursive).

Formula

From Natan Arie Consigli, Apr 10 2016: (Start)

A(0, y) := y+1, A(x+1, 0) := A(x, 1), A(x+1, y+1) := A(x, A(x+1, y));

a(n) = A(n,n).

a(n) = 2[n](n+3)-3 = H_n(2,n+3)-3. (End)

Extensions

Additional comments from Frank Ellermann, Apr 21 2001

Name clarified by Natan Arie Consigli, May 13 2016