Large Numbers — Long Notes

Versions of Ackermann's Function

Ackerman, 1928 (as translated by van Heijenoort):

ack(x,y,z) = { y+z for x = 0 { { 0 for x = 1, z = 0 { { 1 for x = 2, z = 0 { { y for x > 2, z = 0 { { ack(x-1, y, ack(x,y,z-1)) for x,z > 0 Analysis: ack(0,y,z) = y+z ack(1,y,0) = 0 ack(1,y,1) = ack(0,y,ack(1,y,0)) = y+ack(1,y,0) = y = y*1 ack(1,y,2) = ack(0,y,ack(1,y,1)) = y+ack(1,y,1) = y+y = y*2 ack(1,y,n+1) = ack(0,y,ack(1,y,n)) = y+ack(1,y,n) ack(1,y,z) = y*z ack(2,y,0) = 1 ack(2,y,1) = ack(1,y,ack(2,y,0)) = y*ack(2,y,0) = y = y1 ack(2,y,2) = ack(1,y,ack(2,y,1)) = yack(2,y,1) = yy = y2 ack(2,y,n+1) = ack(1,y,ack(2,y,n)) = y*ack(2,y,n) ack(2,y,z) = y^z ack(3,y,0) = y ack(3,y,1) = ack(2,y,ack(3,y,0)) = y^ack(3,y,0) = y^y = y2 ack(3,y,2) = ack(2,y,ack(3,y,1)) = y^ack(3,y,1) = y^(y2) = y3 ack(3,y,n+1) = ack(2,y,ack(3,y,n)) = y^ack(3,y,n) ack(3,y,z) = hy(y,4,z+1) = y(z+1)



Herbert's version (mistranslated from Ackerman's paper):

ack-h(x,y,z) = { y+z for x = 0 { { 0 for x > 0, z = 0 { { y for x > 0, z = 1 { { ack-h(x-1, y, ack-h(x,y,z-1)) for x > 0, z > 1



Rosza Peter (also called Rosa Politzer) simplified it to the following two-argument version in 1935:

ack-po(a,b) = { 2b+1 , for a = 0 { { ack-p(a-1, 1) , for a > 0, b = 0 { { ack-p(a-1, ack-p(a,b-1)) , for a,b > 0



Raphael M. Robinson simplified Peter's version in 1948:

ack-p(a,b) = { b+1 , for a = 0 { { ack-p(a-1, 1) , for a > 0, b = 0 { { ack-p(a-1, ack-p(a,b-1)) , for a,b > 0 Analysis: ack-p(0,b) = b + 1 ack-p(1,0) = ack-p(0,1) = 2 ack-p(1,b) = ack-p(0, ack-p(1, b-1)) = ack-p(1, b-1) + 1 using induction: ack-p(1,0) = 2 = 0 + 2 ack-p(1,1) = 2 + 1 = 1 + 2 ack-p(2,1) = 3 + 1 = 2 + 2 .'. ack-p(1,b) = b + 2 = 2+(b+3) - 3 ack-p(2,0) = ack-p(1,1) = 3 ack-p(2,b) = ack-p(1, ack-p(2, b-1)) = ack-p(2, b-1) + 2 using induction: ack-p(2,0) = 3 = 0 + 3 ack-p(2,1) = 3 + 2 = 2 + 3 ack-p(2,2) = 5 + 2 = 4 + 3 .'. ack-p(2,b) = 2b + 3 = 2×(b+3) - 3 ack-p(3,0) = ack-p(2,1) = 5 = 23 - 3 ack-p(3,b) = ack-p(2, ack-p(3, b-1)) = 2*ack-p(3, b-1) + 3 using induction: ack-p(3,0) = 5 = 2^3 - 3 ack-p(3,1) = 2*5 - 3 = 2^4 - 3 ack-p(3,2) = 2*13 - 3 = 2^5 - 3 .'. ack-p(3,b) = 2(b+3) - 3 = 8×2b - 3 ack-p(4,0) = ack-p(3,1) = 13 ack-p(4,b) = ack-p(3, ack-p(4, b-1)) = 2(ack-p(4, b-1) + 3) - 3 using induction: ack-p(4,0) = 16 - 3 = 23 - 3 ack-p(4,1) = 2^16 - 3 = 24 - 3 ack-p(4,2) = 2^65536 - 3 = 25 - 3 .'. ack-p(4,b) = 2(b+3) - 3 using induction ack-p(0,b) = successor(b+3) - 3 = hy(2,0,b+3) - 3 ack-p(1,b) = 2 + (b+3) - 3 = hy(2,1,b+3) - 3 ack-p(2,b) = 2 * (b+3) - 3 = hy(2,2,b+3) - 3 ack-p(3,b) = 2 ^ (b+3) - 3 = hy(2,3,b+3) - 3 .'. ack-p(a,b) = hy(2,a,b+3) - 3



Buck, 1963:

ack-b(x,y) = { y+1 , for x=0 { { 2 , for x=1, y=0 { { 0 , for x=2, y=0 { { 1 , for x>2, y=0 { { ack-b(x-1,ack-b(x,y-1)) for x,y > 0

This definition gives the rather pretty results:

ack-b(0,y) = 2(0)y = y+1
ack-b(1,y) = 2(1)y = y+2
ack-b(2,y) = 2(2)y = 2y
ack-b(3,y) = 2(3)y = 2y
ack-b(4,y) = 2y
ack-b(x,y) = 2y



Meyer and Ritchie, 1967:

ack-mr(x,z) = { 1 for z=0 { { 2 for x=0, z=1 { { z+2 for x=0, z>1 { { ack-mr(x-1, ack-mr(z,z-1)) for x,z > 0



Robert Munafo, 1998: a cleaner form of ack-p() with the arguments reversed. (It is "cleaner" because its values more closely resemble the dyadic operators)

ack-p2(a,b) = { 2a for b = 1 { { 2 for a = 1, b > 1 { { ack-p2(ack-p2(a-1,b), b-1) for a,b > 1

which yields to analysis as follows:

ack-p2(a,1) = 2a ack-p2(1,b) = 2 ack-p2(a,2) = ack-p2(ack-p2(a-1,2), 1) = 2*ack-p2(a-1,2) and by induction, ack-p2(a,2) = 2^a ack-p2(a,3) = ack-p2(ack-p2(a-1,3), 2) = 2^ack-p2(a-1,3) and by induction, ack-p2(a,3) = 2a ack-p2(a,4) = ack-p2(ack-p2(a-1,4), 3) = 2ack-p2(a-1,4) and by induction, ack-p2(a,4) = 2a and by induction, ack-p2(a,b) = hy(2,a+1,b)



References:

J. Cowles and T. Bailey, "Several Versions of Ackermann's Function", web page



Relating ack(x,y,z) to ack-h(x,y,z):

ack(0,y,z) = y+z = ack-h(0,y,z) for y>=0, z>=0

ack(1,y,z) = y*z = ack-h(1,y,z) for y>=0, z>=0

ack(2,y,z) = y^z = ack-h(2,y,z) for y>=0, z>0

ack(3,y,z) = ack-h(3,y,z+1) for y>=0, z>0

For x>3, ack(x,y,z) and ack-h(x,y,z) are difficult to compare.



analysis of ack-h: For all nonnegative integers x, y, and z, ack-h( x, y, 0 ) equals if x=0 then y else 0 ; ack-h( x, y, 1 ) equals if x=0 then y+1 else y ; ack-h( 0, y, z ) equals y+z ; ack-h( 1, y, z ) equals y*z ; ack-h( 2, y, z ) equals if z=0 then 0 else y^z ; ack-h( 3, y, z ) equals if z=0 then 0 else iter-exp(y,z) ; ack-h( x, 2, 2 ) equals 4 . in general, ack-h(x,y,z) = hy(y,x+1,z)

The Meyer and Ritchie version (1967) of Ackermann's function may be defined recursively on the nonnegative integers by ack-mr( x, z ) <= if z=0 then 1 else if x=0 and z=1 then 2 else if x=0 and z>1 then z+2 else ack-mr( x-1, ack-mr(z,z-1) ). Then for all nonnegative integers x and z, ack-mr( x, 0 ) equals 1 ; ack-mr( 0, z ) equals if z=0 then 1 else if z=1 then 2 else 2+z ; ack-mr( 1, z ) equals if z=0 then 1 else 2*z ; ack-mr( 2, z ) equals 2^z ; ack-mr( 3, z ) equals iter-exp(2,z) ; ack-mr( x, 1 ) equals 2 ; ack-mr( x, 2 ) equals 4 .

The Z. Manna version (1974) of Ackermann's function may be defined recursively on the nonnegative integers by ack-m( x, z ) <= if x*z = 0 then x+z+1 else ack-m( x-1, ack-m( x,z-1) ). Then for all nonnegative integers z, ack-m( 0, z ) equals z+1 ; ack-m( 1, z ) equals z+2 ; ack-m( 2, z ) equals 2*z + 3 ; ack-m( 3, z ) equals 7*(2^z) - 3 ; ack-m( 4, z ) equals h(2,z) - 3 . Here the function h is defined recursively on the nonnegative integers by h( x, z ) <= if z=0 then y^3 else 7*( y^[h(y,z-1)-3] ).

Since everyone else has a version of Ackermann's function, it should cause little or no harm if we also define a version. ack-cb( x, y, z ) <= if x= 0 then y+z else if x=1 and z=0 then 0 else if x>1 and z=0 then 1 else ack-cb( x-1, y, ack-cb(x,y,z-1) ). Then for all nonnegative integers x, y, and z, ack-cb( x, y, 0 ) equals if x=0 then y else if x=1 then 0 else 1 ; ack-cb( 0, y, z ) equals y+z ; ack-cb( 1, y, z ) equals y*z ; ack-cb( 2, y, z ) equals y^z ; ack-cb( 3, y, z ) equals iter-exp(y,z) ; ack-cb( x, y, 1 ) equals if x=0 then y+1 else y ; ack-cb( x, 2, 2 ) equals 4 .

Then for all nonnegative integers x, y, and z, ack-h( x, y, z+1 ) equals ack-cb( x, y, z+1 ) ; ack-mr( x, z+2 ) equals ack-cb( x, 2, z+2 ) equals ack-h( x, 2, z+2 ) ; ack-p( x+1, z ) equals ack-mr( x, z+3 ) - 3 equals ack-h( x, 2, z+3 ) - 3 equals ack-cb( x, 2, z+3 ) - 3 .



s.13