A143797 Ackermann-Buck function, defined recursively by A(0,n) = n+1, A(1,0) = 2, A(2,0) = 0, A(n+3,0) = 1, A(m+1,n+1) = A(m,A(m+1,n)) for any nonnegative integers n, m. Table read by antidiagonals, the second term being A(0,1).

1, 2, 2, 3, 3, 0, 4, 4, 2, 1, 5, 5, 4, 2, 1, 6, 6, 6, 4, 2, 1, 7, 7, 8, 8, 4, 2, 1, 8, 8, 10, 16, 16, 4, 2, 1, 9, 9, 12, 32, 65536, 65536, 4, 2, 1, 10, 10, 14, 64

Offset: 0

Author

Benoit Jubin, Sep 01 2008

Keywords

• nonn
• tabl

Comments

The next term is 2^^5 = 2^2^2^2^2 = 2^65536.

This is a computable function that is not primitive recursive.

The sequence defined in [Boolos] satisfies B(m,n)=A(m+1,n) for positive m,n.

References

• R. Peter, Rekursive Funktionen in der Komputer-Theorie. Budapest: Akad. Kiado, 1951.

Links

• W. Ackermann, Zum Hilbertschen Aufbau der reellen Zahlen, Math. Ann. 99 (1928), 118-133.
• G. Boolos, A curious inference, Journal of Philosophical Logic 16 (1987), 1-12.
• R. C. Buck, Mathematical induction and recursive definitions, Amer. Math. Monthly, 70 (1963), 128-135.
• Eric Weisstein's World of Mathematics, Ackermann function.
• Wikipedia, Ackermann function.

Crossrefs

A001695(n)=A(n, n). Cf. A143796.

Formula

T(n,0) = 1 if n>=3.

T(n,1) = 2 if n>=2.

T(n,2) = 4 if n>=1.

T(1,n) = 2+n.

T(2,n) = 2*n.

T(3,n) = 2^n.

T(4,n) = 2^^n (a power tower of n two's) = A014221(n+1).