## FANDOM

10,818 Pages

This is the general proof of the Strong D Function growth rate. It will focus on 3 parameter functions of the form D(l,m,n) and the proof will be extended later for larger numbers of parameters.

## Strong D Functions D(m,n) with 2 Parameters

For 2 parameters the Strong D Function is the same as the Deeply Nested Ackermann Function which uses the small d notation. Refer to the Comparison Rule C1 on that blog for the proof of the following:

$$d(m,n) >> f_{m-1}(n+2)$$

then

$$D(4,1) >> f_{3}(3) = f_{\omega}(3)$$

$$D(n+1,n+1) >> f_n(n+3) >> f_n(n) = f_{\omega}(n)$$ This is the growth rate of the 2 parameter function

## Strong D Functions D(l,m,n) with 3 Parameters

Lets start by comparing $$D(1,0,3)$$ to $$f_{\omega}(3)$$

$$D(1,0,0) = D(0,D(0,1,1),D(0,1,1)) = D(D(1,1),D(1,1)) = D(4,4) >> f_{\omega}(3)$$

$$D(1,0,1) = D(0,D(1,0,0),D(1,0,0)) = D(D(4,4),D(4,4)) >> f_{\omega}(D(4,4))$$

$$>> f_{\omega}(f_{\omega}(3)) >> f_{\omega}^2(3)$$

$$D(1,0,2) = D(0,D(1,0,1),D(1,0,1)) >> f_{\omega}(D(1,0,1)) >> f_{\omega}(f_{\omega}^2(3)) >> f_{\omega}^3(3)$$

First proof: $$D(1,0,n) >> f_{\omega}^4(n)$$

$$D(1,0,3) = D(0,D(1,0,2),D(1,0,2)) >> f_{\omega}(D(1,0,2)) >> f_{\omega}(f_{\omega}^3(3)) = f_{\omega}^4(3)$$

assume

$$D(1,0,n-1) >> f_{\omega}^4(n-1)$$

then

$$D(1,0,n) = D(0,D(1,0,n-1),D(1,0,n-1)) >> f_{\omega}(D(1,0,n-1)) >> f_{\omega}(f_{\omega}^4(n-1))$$

$$= f_{\omega}^4(f_{\omega}(n-1)) >> f_{\omega}^4(n)$$

Next calculation - getting to $$\omega+1$$

$$D(1,0,n+1) = D(0,D(1,0,n),D(1,0,n)) >> f_{\omega}(D(1,0,n)) >> f_{\omega}(f_{\omega}^4(n)) = f_{\omega}^5(n)$$

$$D(1,0,n+p) = D(0,D(1,0,n+p),D(1,0,n+p)) >> f_{\omega}^{p+4}(n)$$

$$D(1,0,n+n-4) >> f_{\omega}^{n-4+4}(n) = f_{\omega}^n(n) = f_{\omega+1}(n)$$

Second proof: $$D(1,m,0) >> f_{\omega}^m(f_{\omega+1}(m))$$

$$D(1,3,0) = D(0,D(1,2,3),D(1,2,3)) >> D(1,0,8) = D(1,0,6+6-4) >> f_{\omega+1}(6)$$

$$= f_{\omega}^6(6) = f_{\omega}^3(f_{\omega}^3(6) >> f_{\omega}^3(f_{\omega}^3(3)) = f_{\omega}^3(f_{\omega+1}(3))$$

assume

$$D(1,m-1,0) >> f_{\omega}^{m-1}(f_{\omega+1}(m-1))$$

then

$$D(1,m,0) = D(0,D(1,m-1,m),D(1,m-1,m)) >> f_{\omega}(D(1,m-1,m))$$

$$>> f_{\omega}(f_{\omega}(D(1,m-1,m-1))$$

$$>> f_{\omega}^2(f_{\omega}(D(1,m-1,m-2)) >> f_{\omega}^3(f_{\omega}(D(1,m-1,m-3))$$

$$>> f_{\omega}^m(f_{\omega}(D(1,m-1,m-m)) = f_{\omega}^{m+1}(D(1,m-1,0))$$

$$>> f_{\omega}^{m+1}(f_{\omega}^{m-1}(f_{\omega+1}(m-1))) = f_{\omega}^{m.2}(f_{\omega}^{m-1}(m-1))$$

$$= f_{\omega}^{m.2+m-2}(f_{\omega}(m-1)) >> f_{\omega}^{m.2+m-2}(m) >> f_{\omega}^{m.2-2}(f_{\omega}^m(m))$$

$$>> f_{\omega}^m(f_{\omega}^m(m)) = f_{\omega}^m(f_{\omega+1}(m))$$

Next calculation - general formula for $$D(1,m,n)$$

$$D(1,m,1) = D(D(1,m,0),D(1,m,0)) >> f_{f_{\omega}(D(1,m,0))}(f_{\omega}(D(1,m,0))) = f_{\omega}(D(1,m,0))$$

$$>> f_{\omega}(f_{\omega}^m(f_{\omega+1}(m))) = f_{\omega}^{m+1}(f_{\omega+1}(m))$$

$$D(1,m,n) >> f_{\omega}^{m+n}(f_{\omega+1}(m))$$

Next calculation - general formula for $$D(1,n,n)$$

$$D(1,n,n) >> f_{\omega}^{n.2}(f_{\omega+1}(n))$$

Next calculation - $$D(2,0,0)$$

$$D(2,0,0) = D(1,D(1,2,2),D(1,2,2)) >> f_{\omega}^{D(1,2,2)}(f_{\omega+1}(D(1,2,2)))$$

$$>> f_{\omega+1}(D(1,2,2)) >> f_{\omega+1}(f_{\omega}^{2.2}(f_{\omega+1}(2))))$$

$$= f_{\omega+1}(f_{\omega}^4(f_{\omega}^2(2))) = f_{\omega+1}(f_{\omega}^5(f_{\omega}(2))))$$

$$>> f_{\omega+1}(f_{\omega}^5(5)) = f_{\omega+1}(f_{\omega+1}(5)) = f_{\omega+1}^2(5)$$

Third proof: $$D(2,0,n) >> f_{\omega+1}^2(n)$$

$$D(2,0,5) >> D(2,0,0) >> f_{\omega+1}^2(5)$$

assume

$$D(2,0,n-1) >> f_{\omega+1}^2(n-1)$$

then

$$D(2,0,n) = D(1,D(2,0,n-1),D(2,0,n-1)) >> f_{\omega}^{D(2,0,n-1).2}(f_{\omega+1}(D(2,0,n-1)))$$

$$>> f_{\omega+1}(f_{\omega+1}^2(n-1)) = f_{\omega+1}^2(f_{\omega+1}(n-1))$$

$$>> f_{\omega+1}^2(n)$$

Next calculation - getting to $$\omega+2$$

$$D(2,0,n+1) = D(1,D(2,0,n),D(2,0,n)) >> f_{\omega}^{D(2,0,n).2}(f_{\omega+1}(D(2,0,n)))$$

$$>> f_{\omega+1}(D(2,0,n))) >> f_{\omega+1}(f_{\omega+1}^2(n))) = f_{\omega+1}^3(n))$$

$$D(2,0,n+p) = D(1,D(2,0,n+p),D(2,0,n+p)) >> f_{\omega+1}^{p+2}(n))$$

$$D(2,0,n+n-2) >> f_{\omega+1}^{n-2+2}(n) = f_{\omega+2}(n)$$

Fourth proof: $$D(2,m,0) >> f_{\omega+1}^m(f_{\omega+2}(m))$$

$$D(2,3,0) = D(1,D(2,2,3),D(2,2,3)) >> D(1,D(2,0,8),D(2,0,8))$$

$$>> f_{\omega}^{D(2,0,8).2}(f_{\omega+1}(D(2,0,8))) >> f_{\omega+1}(D(2,0,8))$$

$$= f_{\omega+1}(D(2,0,5+5-2)) >> f_{\omega+1}(f_{\omega+2}(5))$$

$$= f_{\omega+1}(f_{\omega+1}^5(5)) = f_{\omega+1}^3(f_{\omega+1}^3(5)) >> f_{\omega+1}(f_{\omega+1}^3(3))$$

$$= f_{\omega+1}^3(f_{\omega+2}(3))$$

assume

$$D(2,m-1,0) >> f_{\omega+1}^{m-1}(f_{\omega+2}(m-1))$$

then

$$D(2,m,0) = D(1,D(2,m-1,m),D(2,m-1,m)) >> f_{\omega}^{D(2,m-1,m).2}(f_{\omega+1}(D(2,m-1,m)))$$

$$>> f_{\omega+1}(D(2,m-1,m)) >> f_{\omega+1}(f_{\omega+1}(D(2,m-1,m-1))$$

$$>> f_{\omega+1}^2(f_{\omega+1}(D(2,m-1,m-2)) >> f_{\omega+1}^3(f_{\omega+1}(D(2,m-1,m-3))$$

$$>> f_{\omega+1}^m(f_{\omega+1}(D(2,m-1,m-m)) = f_{\omega+1}^{m+1}(D(2,m-1,0))$$

$$>> f_{\omega+1}^{m+1}(f_{\omega+1}^{m-1}(f_{\omega+1}^{m-1}(f_{\omega+2}(m-1))))$$

$$>> f_{\omega+1}^{m.2}(f_{\omega+1}^{m-1}(f_{\omega+2}(m-1))) = f_{\omega+1}^{m.3-1}(f_{\omega+1}^{m-1}(m-1))$$

$$= f_{\omega+1}^{m.4-3}(f_{\omega+1}(m-1)) >> f_{\omega+1}^{m.4-3}(m) = f_{\omega+1}^{m.3-3}(f_{\omega+1}^m(m))$$

$$= f_{\omega+1}^{m.3-3}(f_{\omega+2}(m)) >> f_{\omega+1}^m(f_{\omega+2}(m))$$

Next calculation - general formula for $$D(2,m,n)$$

$$D(2,m,1) = D(1,D(2,m,0),D(2,m,0)) >> f_{\omega}^{D(2,m,0).2}(f_{\omega+1}(D(2,m,0),)) >> f_{\omega+1}(D(2,m,0))$$

$$>> f_{\omega+1}(f_{\omega+1}^m(f_{\omega+2}(m))) = f_{\omega+1}^{m+1}(f_{\omega+2}(m))$$

$$D(2,m,n) >> f_{\omega+1}^{m+n}(f_{\omega+2}(m))$$

Next calculation - general formula for $$D(2,n,n)$$

$$D(2,n,n) >> f_{\omega+1}^{n.2}(f_{\omega+2}(n))$$

Fifth proof: $$D(l,0,n) >> f_{\phi}^2(n)$$

assume

$$D(l-1,0,n) >> f_{\phi-1}^2(n))$$

$$D(l-1,m,n) >> f_{\phi-1}^{m+n}(f_{\phi}(m))$$

then

$$D(l,0,0) = D(l-1,D(l,l-1,l-1),D(l,l-1,l-1)) >> f_{\phi-1}^{D(l,l-1,l-1))+D(l,l-1,l-1))}(f_{\phi}(D(l,l-1,l-1))))$$

$$>> f_{\phi}(D(l,l-1,l-1)) >> f_{\phi}(D(l-1,D(l,l-1,l-2),D(l,l-1,l-2)))$$

$$>> f_{\phi}(f_{\phi-1}^{D(l,l-1,l-2)+D(l,l-1,l-2)}(f_{\phi}(D(l,l-1,l-2)))))$$

$$>> f_{\phi}(f_{\phi-1}(f_{\phi}(D(l,l-1,l-2)))) >> f_{\phi}(f_{\phi}(D(l,l-1,l-2))) >> f_{\phi}^2(D(l,l-1,l-2))$$

$$>> f_{\phi}^2(3)$$

$$D(l,0,3) >> D(l,0,0) >> f_{\phi}^2(3))$$

assume

$$D(l,0,n-1) >> f_{\phi}^2(n-1)$$

then

$$D(l,0,n) = D(l-1,D(l,0,n-1),D(l,0,n-1)) >> f_{\phi-1}^{D(l,0,n-1))+D(l,0,n-1))}(f_{\phi}(D(l,0,n-1))))$$

$$>> f_{\phi}(D(l,0,n-1)) >> f_{\phi}(f_{\phi}^2(n-1))$$

$$= f_{\phi}^2(f_{\phi}(n-1)) >> f_{\phi}^2(n)$$

Sixth proof: $$D(l,m,n) >> f_{\phi}^{m+n}(f_{\phi+1}(m))$$

assume

$$D(l-1,m,n) >> f_{\phi-1}^{m+n}(f_{\phi}(m))$$

$$D(l,0,n) >> f_{\phi}^2(n)$$

then

$$D(l,3,0) = D(l-1,D(l,2,3),D(l,2,3)) >> f_{\phi-1}^{D(l,2,3).2}(f_{\phi}(D(l,2,3)))$$

$$>> f_{\phi}(D((l,2,3)) >> f_{\phi}(D(l-1,D(l,2,2),D(l,2,2)))$$

$$>> f_{\phi}(f_{\phi-1}^{D(l,2,2)+D(l,2,2)}(f_{\phi}(D(l,2,2))))$$

$$>> f_{\phi}(f_{\phi}(D(l,2,2))) >> f_{\phi}^2(D(l-1,D(l,2,1),D(l,2,1))$$

$$>> f_{\phi}^2(D(l,2,1)) >> f_{\phi}^2(f_{\phi}(D(l-1,D(l,2,0),D(l,2,0)))$$

$$>> f_{\phi}^3(D(l,2,0)) >> f_{\phi}^3(f_{\phi}(D(l-1,D(l,1,2),D(l,1,2)))$$

$$>> f_{\phi}^4(D(l,1,2)) >> f_{\phi}^4(D(l,0,3)) >> f_{\phi}^4(f_{\phi}^2(3)) = f_{\phi}^3(f_{\phi}^3(3))$$

$$= f_{\phi}^3(f_{\phi+1}(3))$$

assume

$$D(l,m-1,0) >> f_{\phi}^m(f_{\phi+1}(m-1))$$

then

$$D(l,m,n) = D(l-1,D(l,m,n-1),D(l,m,n-1)) >> f_{\phi-1}^{D(l,m,n-1)+D(l,m,n-1)}(f_{\phi}(D(l,m,n-1)))$$

$$>> f_{\phi}(D((l,m,n-1)) >> f_{\phi}(D(l-1,D(l,m,n-2),D(l,m,n-2)))$$

$$>> f_{\phi}(f_{\phi-1}^{D(l,m,n-2)+D(l,m,n-2)}(f_{\phi}(D(l,m,n-2))))$$

$$>> f_{\phi}(f_{\phi}(D(l,m,n-2))) >> f_{\phi}^2(D(l-1,D(l,m,n-3),D(l,m,n-3))$$

$$>> f_{\phi}^2(D(l,m,n-3)) >> f_{\phi}^2(f_{\phi}(D(l-1,D(l,m,n-4),D(l,m,n-4)))$$

...

$$>> f_{\phi}^{n-1}(D(l,m,n-n)) >> f_{\phi}^{n-1}(D(l,m,0) >> f_{\phi}^{n-1}(f_{\phi}(D(l-1,D(l,m-1,m),D(l,m-1,m)))$$

$$>> f_{\phi}^n(D((l,m-1,m)) >> f_{\phi}^n(D(l-1,D(l,m-1,m-1),D(l,m-1,m-1)))$$

$$>> f_{\phi}^{n+1}(D((l,m-1,m-1)) >> f_{\phi}^{n+1}(D(l-1,D(l,m-1,m-2),D(l,m-1,m-2)))$$

$$>> f_{\phi}^{n+2}(D((l,m-1,m-2)) >> f_{\phi}^{n+1}(D(l-1,D(l,m-1,m-3),D(l,m-1,m-3)))$$

...

$$>> f_{\phi}^{n+m}(D((l,m-1,m-m)) >> f_{\phi}^{n+m}(D(l-1,m-1,0)) >> f_{\phi}^{n+m}(f_{\phi}^m(f_{\phi+1}(m-1)))$$

$$= f_{\phi}^{n+m.2}(f_{\phi+1}(m-1)) = f_{\phi}^{n+m.2}(f_{\phi}^{m-1}(m-1))$$

$$= f_{\phi}^{n+m.3-2}(f_{\phi}(m-1)) >> f_{\phi}^{n+m.3-2}(m) = f_{\phi}^{n+m.2-2}(f_{\phi}^{m}(m))$$

$$= f_{\phi}^{n+m.2-2}(f_{\phi+1}(m))$$

## (outdated) References

The following references are likely to be outdated because the above proofs and examples will be more reliable. Please keep this in mind if you refer to any of these blogs.