Large Numbers — Long Notes

Versions of Ackermann's Function

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 1992.[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 > 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) 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 = y¹ ack(2,y,2) = ack(1,y,ack(2,y,1)) = y×ack(2,y,1) = y×y = y² 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 > 1

Analysis (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×(y×y) 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⁽ⁿ⁺¹⁾z, where ⁽ⁿ⁺¹⁾ 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 > 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

Recursive calls on 0: ack-p(0,0) = 1; ack-p(1,1) = 3; ack-p(3,3) = 61; ack-p(61,61) = 2⁽⁶¹⁾64 - 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

Recursive calls on 0: ack-b(0,0) = 1; ack-b(1,1) = 3; ack-b(3,3) = 8; ack-b(8,8) = 2⁽⁸⁾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 > 0

Analysis:

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^④z

So we have ack-mr(n,z) = 2⁽ⁿ⁺¹⁾z where ⁽ⁿ⁺¹⁾ 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=0

Analysis:

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; ack-p2(4,4) = 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 > 0

Analysis: 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 > 0

Analysis:

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×(2×2+1)+1 = 11 ack-kb(3,2) = ack-kb(ack-kb(2, 2), 1) = ack-kb(2×(2×2+1)+1, 1) = 2×(2×(2×2+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) = 3×2^(3×2^3-1)-1 = 25165823 ≈ 2^24.58 ≈ 2^④4 ack-kb(3,3) = ack-kb(ack-kb(2, 3), 2) = ack-kb(3×2^(3×2^3-1)-1, 2) = 3×2^(3×2^(3×2^3-1)-1)-1 ≈ 1.1633×10^7575668 ≈ 2^{2^24.58} ≈ 2^④5 Using a three-argument iterated exponential function, Lew Baxter showed that this can be generalized to: ack-kb(x,3) = (3/2) ie3(√8, x, 8/3) - 1 where ie3(a, b, c) is the iterated exponential function: ie3(a, b, c) = a ^ (a ^ ( a ^ ( ... ^ c))) (with b copies of 'a') Using a program like Hypercalc demonstrates the accuracy of the approximation 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

Lew Baxter's Derivation For ack-kb(x,3)

Given the identity (derived above) for ack-kb(x,2) :

ack-kb(x,2) = 3×2^x-1

and the "three-argument iterated exponential" function ie3():

ie3(a, b, c) = a ^ (a ^ ( a ^ ( ... ^ c))) (with b copies of 'a')

reader Lew Baxter gives[3] the closed-form solution:

ack-kb(x,3) = (3/2) ie3(√8, x, 8/3) - 1

We can show this is true using induction. First we need to compute ack-kb(0,3) and ack-kb(1,3) directly. From above:

ack-kb(0, 3) = 3 ack-kb(1, 3) = ack-kb(ack-kb(1-1,3), 3-1) = ack-kb(ack-kb(0,3), 2) = ack-kb(3, 2) = 3×2³ - 1 = 24 - 1 = 23

Then we show that the formula works for ack-kb(1,3):

(3/2) ie3(√8, 1, 8/3) - 1 = (3/2) [√8^(8/3)] - 1 = (3/2)×2^{[(3/2) (8/3)]} - 1 = (3/2)×2^(8/2) - 1 = (3/2)×16 - 1 = 23

Now we can use induction to prove the general case:

IF ack-kb(x, 3) = (3/2) ie3(√8, x, 8/3) - 1 THEN ack-kb(x+1, 3) = ack-kb(ack-kb((x+1)-1, 3), 2) = ack-kb(ack-kb(x, 3), 2) = 3×2^ack-kb(x,3) - 1 = (3/2) × 2^{[ack-kb(x, 3) + 1]} - 1 = (3/2) √8^{[(2/3) (ack-kb(x,3) + 1)]} - 1 = (3/2) √8^{[(2/3) ((3/2) ie3(√8,x,8/3) - 1 + 1)]} - 1 = (3/2) √8^{[(2/3) (3/2) ie3(√8,x,8/3)]} - 1 = (3/2) √8^{ie3(√8,x,8/3)} - 1 = (3/2) × ie3(√8, x+1, 8/3) - 1 .'. ack-kb(x+1,3) = (3/2) ie3(√8, x+1, 8/3) - 1

Since the formula works for ack-kb(x,3) when x=1, and iteratively for all higher x, it works for all x greater than 0.

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, 1992. At www.cs.utexas.edu/users/boyer/ftp/nqthm/nqthm-1992/examples/basic/peter.events

[3] Lew Baxter, personal correspondence, 2012.

Google+

mrob27

@mrob_27

This work is licensed under a Creative Commons Attribution-NonCommercial 2.5 License. Details here s.13