Much of the following information, including the names like ack-h, originate with John Cowles, "Ackermann's Original Function" and "more on Ackermann", which were email messages sent to Robert S. Boyer, and included as comments in an Nqthm file by Boyer in 1994.[2]
Ackermann, 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 > 0Analysis:
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) so by induction, 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) so by induction, 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) so by induction, ack(3,y,z) = hy(y,4,z+1) = y④(z+1)
The Edelsbrunner/Herbert version is from Edelsbrunner and Herbert, "Algorithms in Combinatorial Geometry", 1987. It is apparently mistranslated from Ackermann'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 > 1Analysis (mostly from [1]):
ack-h(0,y,z) = y+z by definition ack-h(1,y,0) = 0 by definition ack-h(1,y,1) = ack-h(0,y,ack-h(1,y,0)) = ack-h(0,y,0) = y ack-h(1,y,2) = ack-h(0,y,ack-h(1,y,1)) = ack-h(0,y,y) = y+y ack-h(1,y,3) = ack-h(0,y,ack-h(1,y,2)) = ack-h(0,y,y) = y+(y+y) by induction, ack-h(1,y,z) = y*z ack-h(2,y,0) = 0 by definition ack-h(2,y,1) = y by definition ack-h(2,y,2) = ack-h(1,y,ack-h(2,y,1)) = ack-h(1,y,y) = y*y ack-h(2,y,3) = ack-h(1,y,ack-h(2,y,2)) = ack-h(1,y,y*y) = y(yy) by induction, ack-h(2,y,z) = y^z (except when z=0) ack-h(3,y,0) = 0 by definition ack-h(3,y,1) = y by definition ack-h(3,y,2) = ack-h(2,y,ack-h(3,y,1)) = ack-h(2,y,y) = y^y ack-h(3,y,3) = ack-h(2,y,ack-h(3,y,2)) = ack-h(2,y,y^y) = y^(y^y) by induction, ack-h(3,y,z) = y④z (except when z=0) ack-h(4,y,0) = 0 by definition ack-h(4,y,1) = y by definition ack-h(4,y,2) = ack-h(3,y,ack-h(4,y,1)) = ack-h(3,y,y) = y④y ack-h(4,y,3) = ack-h(3,y,ack-h(4,y,2)) = ack-h(3,y,y④y) = y④(y④y) by induction, ack-h(4,y,z) = y⑤z (except when z=0)In general, ack-h(n,y,z) = hy(y,n+1,z) = y(n+1)z, where (n+1) is the generalized hyper operator.
Relationship between ack(x,y,z) and 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) do not compare directly.
Rosza Peter (also called Rosa Politzer) simplified Ackermann's three-argument function 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. This version is significant in being the first to invoke only the successor f(x)=x+1 and predecessor f(x)=x-1 functions:
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 > 0Analysis:
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 = 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) - 3Recursive calls on 0: ack-p(0,0) = 1; ack-p(1,1) = 3; ack-p(3,3) = 61
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 > 0This definition gives the rather pretty results:
ack-b(0,y) = 2(0)y = y+1
ack-b(1,y) = 2①y = y+2
ack-b(2,y) = 2②y = 2y
ack-b(3,y) = 2③y = 2y
ack-b(4,y) = 2④y
ack-b(x,y) = 2ⓧy
Recursive calls on 0: ack-b(0,0) = 1; ack-b(1,1) = 3; ack-b(3,3) = 8
Meyer and Ritchie, 1967 (note arguments "(x,z-1)" are corrected from the original source which had "(z,z-1)"):
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(x,z-1)) for x,z > 0Analysis:
ack-mr(x,0) = 1 by definition ack-mr(0,1) = 2 by definition ack-mr(1,1) = ack-mr(0, ack-mr(1,0)) = ack-mr(0,1) = 2 ack-mr(2,1) = ack-mr(1, ack-mr(2,0)) = ack-mr(1,1) = 2 by induction, ack-mr(x,1) = 2 ack-mr(0,2) = 2+2 by definition = 4 ack-mr(1,2) = ack-mr(0, ack-mr(1,1)) = ack-mr(0,2) = 4 ack-mr(2,2) = ack-mr(1, ack-mr(2,1)) = ack-mr(1,2) = 4 by induction, ack-mr(x,2) = 4 ack-mr(0,z) = 2+z for z>=2 (by definition) ack-mr(1,0) = 1 by definition ack-mr(1,1) = 2 by (x,1) case above ack-mr(1,2) = 4 by (x,2) case above ack-mr(1,3) = ack-mr(0, ack-mr(1,2)) = ack-mr(0,4) = 6 ack-mr(1,4) = ack-mr(0, ack-mr(1,3)) = ack-mr(0,6) = 8 ack-mr(1,5) = ack-mr(0, ack-mr(1,4)) = ack-mr(0,8) = 10 by induction, ack-mr(1,z) = 2*z ack-mr(2,0) = 1 by definition ack-mr(2,1) = 2 by (x,1) case above ack-mr(2,2) = 4 by (x,2) case above ack-mr(2,3) = ack-mr(1, ack-mr(2,2)) = ack-mr(1,4) = 2*4 = 8 ack-mr(2,4) = ack-mr(1, ack-mr(2,3)) = ack-mr(1,8) = 2*8 = 16 by induction, ack-mr(2,z) = 2^z ack-mr(3,0) = 1 ack-mr(3,1) = 2 by (x,1) case above ack-mr(3,2) = 4 by (x,2) case above ack-mr(3,3) = ack-mr(2, ack-mr(3,2)) = ack-mr(2,4) = 2^4 = 16 ack-mr(3,4) = ack-mr(2, ack-mr(3,3)) = ack-mr(2,16) = 2^16 = 256 by induction, ack-mr(3,z) = 2④zSo we have ack-mr(n,z) = 2(n+1)z where (n+1) is the generalized hyper operator.
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 { { intentionally undefined for a=0 or b=0Analysis:
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)Recursive calls on 1: ack-p2(1,1) = 2; ack-p2(2,2) = 4
Alteration of Meyer/Ritchie version with the role of the arguments reversed:
ack-mrr(x,z) = { 1 for x=0 { { 2 for z=0, x=1 { { x+2 for z=0, x>1 { { ack-mr(ack-mr(x-1,z), z-1) for x,z > 0Analysis: Same as ack-mr above, just reverse all the arguments.
Kaitlyn Burnell, 2009: This version was created mainly with the goal of creating fastest growth with the least total number of operators, recursive calls, and conditional tests (each of which counts for "one point"). It most closely resembles ack-mrr but is simpler in that ack-kb(n,0)=n+2 for all n:
ack-kb(x,z) = { x+2 for z=0 { { z for x=0, z>0 { { ack-kb(ack-kb(x-1,z), z-1) for x,z > 0Analysis:
ack-kb(a,0) = 2+a ack-kb(0,1) = 1 ack-kb(1,1) = ack-kb(ack-kb(0, 1), 0) = ack-kb(1, 0) = 2+1 ack-kb(2,1) = ack-kb(ack-kb(1, 1), 0) = ack-kb(2+1, 0) = 2+2+1 by induction, ack-kb(a,1) = 2*a+1 ack-kb(0,2) = 2 ack-kb(1,2) = ack-kb(ack-kb(0, 2), 1) = ack-kb(2, 1) = 2*2+1 = 5 ack-kb(2,2) = ack-kb(ack-kb(1, 2), 1) = ack-kb(2*2+1, 1) = 2(22+1)+1 = 11 ack-kb(3,2) = ack-kb(ack-kb(2, 2), 1) = ack-kb(2(22+1)+1, 1) = 2*(2(22+1)+1)+1 = 23 by induction, ack-kb(a,2) = 3*2^a-1 ack-kb(0,3) = 3 ack-kb(1,3) = ack-kb(ack-kb(0, 3), 2) = ack-kb(3, 2) = 3*2^3-1 = 23 ack-kb(2,3) = ack-kb(ack-kb(1, 3), 2) = ack-kb(3*2^3-1, 2) = 32^(32^3-1)-1 = 25165823 ≅ 224.58 ≅ 2④4 ack-kb(3,3) = ack-kb(ack-kb(2, 3), 2) = ack-kb(32^(32^3-1)-1, 2) = 3*2^(32^(32^3-1)-1)-1 ≅ 1.1633×107575668 ≅ 2224.58 ≅ 2④5 An exact closed-form expression is probably impossible here, but continued calculation with a program like Hypercalc demonstrates the accuracy of the general formula ack-kb(a,3) ≅ 2④(a+2) for a>3. A similar and even more messy series of examples can show that ack-kb(a,4) grows about as fast as 2⑤(a+3).Recursive calls on 0: ack-b(0,0) = 2; ack-b(2,2) = 11; ack-b(11,11) ≅ 2⑬14
References:
[1] John Cowles and T. Bailey, "Several Versions of Ackermann's Function", formerly at www.cli.com/ftp/pub/nqthm/nqthm-1987/ackermann.msg but now gone.
[2] Robert S. Boyer, Nqthm lemmas relating Ackermann's original function to R. Peter's variation, www.cs.utexas.edu/users/boyer/ftp/nqthm/nqthm-1992/examples/basic/peter.events
Robert Munafo's home pages on HostMDS (c) 1996-2010 Robert P. Munafo. about contact
This work is licensed under a Creative Commons Attribution 2.5
License. Details here
s.13