Large Numbers -- Long Notes at MROB

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 = y¹ ack(2,y,2) = ack(1,y,ack(2,y,1)) = yack(2,y,1) = yy = y² 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 = y^④2 ack(3,y,2) = ack(2,y,ack(3,y,1)) = y^ack(3,y,1) = y^(y^④2) = y^④3 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 = 2³ - 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×2^b - 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 = 2^④3 - 3 ack-p(4,1) = 2^16 - 3 = 2^④4 - 3 ack-p(4,2) = 2^65536 - 3 = 2^④5 - 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⁽⁰⁾y = y+1
ack-b(1,y) = 2⁽¹⁾y = y+2
ack-b(2,y) = 2⁽²⁾y = 2y
ack-b(3,y) = 2⁽³⁾y = 2^y
ack-b(4,y) = 2^④y
ack-b(x,y) = 2^ⓧy

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) = 2^④a ack-p2(a,4) = ack-p2(ack-p2(a-1,4), 3) = 2^④ack-p2(a-1,4) and by induction, ack-p2(a,4) = 2^⑤a 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