FANDOM


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.

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.