FANDOM


Deeply Nested Ackermann

The Deeply Nested Ackermann function (signified with a lowercase d) is defined by generalizing the Modified Ackermann Function MA() with a variable input parameter array:

\(d(x_1,x_2,x_3,x_4, ... ,x_n)\)

Rules for the d function are similar to MA function rules but generalised as follows:

\(d() = 0\) This is a null function that always returns zero.

\(d(m) = m+1\) This is equivalent to MA(0,m)

The next example is equivalent to the \(MA(m,n)\) function.

\(d(m,n) = MA(m,n)\) And the same rules apply:

\(d(m,n)\) defined as:

◾ \(n+1\) if m=0 ,

◾ \(d(m−1,d(m-1,m))\) if n=0 , or

◾ \(d(m−1, d(m,n−1))\) otherwise.

For 3 parameters, the rules are generalised and extended as follows:

\(d(m_1,m_2,m_3)\) defined as:

◾ \(d(m_{2},m_{3})\) if \(m_1=0\) ,

◾ \(d(m_1−1, d(m_1,m_2-1), d(m_1,m_2,m_3-1))\) if \(m_1>0\) , \(m_2>0\) and \(m_3>0\)

but \(d(m_1,m_2-1)\) is substituted by \(d(m_1-1,m_1)\) if \(m_2=0\)

and \(d(m_1,m_2,m_3-1)\) is substituted by \(d(m_1,m_2-1,m_2)\) if \(m_3=0\)

or \(d(m_1,m_2,m_3-1)\) is substituted by \(d(m_1-1,m_1,m_1)\) if \(m_2=0\) and \(m_3=0\)


General Example

Instead of giving an example for \(d(x_{1},x_{2},x_{3},x_{4})\) next, it is actually easier to follow the general example for:

\(d(x_{1},x_{2},x_{3},x_{4}, ... ,x_{n})\) defined as this deeply nested function:

\(d(x_{1}-1, d(x_{1},x_{2}-1), d(x_{1},x_{2},x_{3}-1), d(x_{1},x_{2},x_{3},x_{4}-1), ..., d(x_{1},x_{2},x_{3},x_{4}, ... ,x_{n}-1)\)

The only substitution rules that need to be followed are:

Leading Zeros rule

L1. \(d(0,0, ...,0,x,y,z)\) is substituted for \(d(x,y,z)\) in all cases

Trailing Zeros rule

T1. \(d(x,y,z,0,0, ... ,-1)\) is substituted for \(d(x,y,z-1,z,z, ... ,z)\) in all cases


Calculated Examples

\(d() = 0\) This is a null function that always returns zero.

\(d(3) = 4\) This is the successor function

\(d(1,2) = 5\) This is equal to MA(1,2) = 2+3

\(d(1,n) >> f_0(n+2)\)

Using the Comparison Rule C1 (at the end of this blog post) we get:

\(d(m,n) >> f_{m-1}(n)\)

\(d(1,0,0)\) is the first non trivial calculation and expands as follows:

\(= d(0,d(0,1),d(0,1,1))\) then apply the Leading Zeros rule

\(= d(d(1),d(1,1)) = d(2,4) = 20\) This is equal to MA(2,4) = 3.4+8

then

\(d(1,0,1) = d(0,d(0,1),d(1,0,0)) = d(d(1),d(1,0,0)) = d(2,20) = 68\) This is equal to MA(2,20) = 3*20+8

and

\(d(1,0,2) = d(2,d(1,0,1)) = d(2,68)\)

next

\(d(1,1,0) = d(0,d(1,0),d(1,0,1)) = d(3,68) >> f_2(68)\)

\(d(1,1,1) = d(0,d(1,0),d(1,1,0)) = d(3,d(3,68)) >> f_2^2(68)\)

\(d(1,1,n) >> f_2^{n+1}(68)\)

\(d(1,2,0) = d(0,d(1,1),d(1,1,2)) >> d(4,f_2^3(68)) >> f_3(f_2^3(68))\)

\(d(1,2,n) >> f_3^{n+1}(f_2^3(68))\)

\(d(1,3,0) = d(0,d(1,2),d(1,2,3)) >> d(5,f_3^4(f_2^3(68))) >> f_4(f_3^4(f_2^3(68)))\)

\(d(1,3,n) >> f_4^{n+1}(f_3^4(f_2^3(68)))\)

or

\(d(1,3,n+p) >> f_4^{n+1}(n) >> f_5(n)\) where \(p << n\)

and

\(d(1,m,n+p) >> f_{m+1}^{n+1}(n) >> f_{m+2}(n)\) where \(p << n\)


Some Comparisons

\(d(3,0) = 59\)

\(d(3,9) >> d(2,16) >> 1,000,000\)

\(d(3,206) >> d(2,324) >>\) Googol

\(d(4,0) = d(3,5099) >> 3^{5099}\)

\(d(1,1,0) = d(3,68) <<\) Googol

\(d(1,1,1) = d(d(1,0),d(1,1,0)) = d(3,d(3,68)) >> 3^{3^{68}} <<\) Googolplex

\(d(1,1,2) = d(d(1,0),d(1,1,1)) = d(3,d(1,1,1)) >> d(3,3^{3^{68}}) >>\) Googolplex

\(d(1,3,0) >> d(6,1) >> g_1\) where \(g_{64} = G\) Graham's number

\(d(1,4,0) = d(6,d(1,3,4)) >> d(6,g_1)\)

\(d(1,4,1) = d(6,d(1,4,0))\)

Comparing d functions with 3 and 2 input parameters we get:

\(d(1,y,z) = d(y+2,d(1,y,z-1))\)

Then

\(d(2,0,0) = d(1,d(1,2),d(1,2,2)) >> d(1,5,f_4(2)) >> f_7(f_4(2))\)

\(d(2,0,1) = d(1,d(1,2),d(2,0,0)) >> d(1,5,f_7(f_4(2))) >> f_7^2(f_4(2))\)

\(d(2,0,n) >> f_7^{n+1}(f_4(2))\)


Graham's Number

The d function can reach \(g_1\), where \(g_{64} = G\) (Graham's number), relatively quickly. As shown above \(d(1,3,0) >> g_1\) .

\(g_0 = 4\) and \(g_1 = 3 \uparrow\uparrow\uparrow\uparrow 3 << f_5(3) = f_{g_0}(3)\)

\(g_2 << f_{g_1}(3)\) and likewise till \(G = g_{64} << f_{g_{63}}(3)\)

In the fast-growing hierarchy, Graham's Number can be shown to be less than \(f_{\omega+1}(64) = f_{\omega}^{64}(64)\). \(G\) is closer to, but still less than \(f_{\omega}^{64}(5)\) .

We need d functions with many more input parameters to reach G (Graham's Number).

\(d(6,1) >> f_5(3) >> g_1\)

\(d( d(6,1), 1) >> g_2\)

\(d(6,1,1)\) we will get \(d(6,1)\) nested in its long expansion and therefore \(d(6,1,1) >> g_2\) by a very great amount.

We can reach \(g_3\) by moving to 4 input parameters

\(d(6,1,1,1) >> g_3\)

We finally reach G (Graham's Number) with 64 input parameters

\(d(6,1,1,1, ..., 1,1) >> G\)


Growth Rate

Using the comparison rule C1 at the end of this blog:

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

we can see the growth rate for:

\(d(n+1,n-2) >> f_n(n)\) or \(f_{\omega}(n)\)

The growth rate for \(d(x_1,x_2,x_3,x_4,...,x_n)\) is comparable to \(f_{\omega+1}(n)\)


Next Blog

To get more impressive growth growths, we can create a strong version of this function. My next blog post introduces the Strong D Function based on the above (weak) d function.


Comparison Rule

A simple way to compare the d function to the Fast-growing hierarchy, is:

Comparison Rule C1. \(d(m,n-2+\delta) >> f_{m-1}(n)\) where \(\delta << n\)

or

\(d(m,n) >> f_{m-1}(n)\)

To illustrate this rule we start with:

\(d(0,n) = f_0(n)\) by definition

\(d(1,0) = d(0,d(0,1)) = f_0(f_0(1)) = f_0^2(1)\)

\(d(1,1) = d(0,d(1,0)) = f_0(f_0^2(1)) = f_0^3(1)\)

\(d(1,2) = d(0,d(1,1)) = f_0^4(1)\)

and

\(d(1,n) = d(0,d(1,n-1)) = f_0^{n+2}(1) = f_0^3(n)\) by definition

then

\(d(2,0) = d(1,d(1,2)) = f_0^3(f_0^3(2)) = f_0^3(f_0(4)) = f_0^4(4) = f_1(4)\)

\(d(2,1) = d(1,d(2,0)) = f_0^3(f_1(4)) = f_0(f_0^2(f_1(4))) = f_0(f_1(5))\) by definition

\(d(2,2) = d(1,d(2,1)) = f_0^3(f_0(f_1(5))) = f_0^2(f_0^2(f_1(5))) = f_0^2(f_1(6)) = f_1(7)\) by definition

and

\(d(2,n) = f_0^{n/2}(f_1(n+4)) >> f_1(n.3/2+4) >> f_1(n+4)\)

then

\(d(2,d(2,n)) >> f_1(f_1(n+4)+4) >> f_1(f_1(n+4)) = f_1^2(n+4)\)

\(d(3,0) = d(2,d(2,3)) >> f_1^2(7)\)

\(d(3,1) = d(2,d(3,0)) >> f_1^3(7) >> f_2(3)\)

\(d(3,2) >> f_1^4(3) = f_1^3(n)\) where \(n <= f_1(7)\)

\(d(3,m) >> f_1^{m+2-p}(n)\) where \(n <= f_1^p(7)\)

\(d(3,n-2+p) >> f_1^{n}(n) >> f_2(n)\) where \(n <= f_1^p(7)\)

then

\(d(m,n-2+\delta) >> f_{m-1}(n)\) where \(\delta << n\)


Alternative Comparison Rule

The growth rate of the d function is comparable to the Fast-growing hierarchy , with this rule:

A1. \(d(x,y) = d(x-1, d(x,y-1)) = d^{y+2}(x-1,x)\)

\(f_x(y) = f_{x-1}^{y}(y)\)

\(f_x(y)\) is greater than \(d(x,y)\) because \(f_2(y) = 2.2^y\) and \(d(2,y) = 3.y + 8\) and both growth functions recursively grow at the same rate for greater values of x.

So we can use this Comparison Rule:

C1. \(f_x(y+2) << d(x+1,y)\)

because \(f_{x-1}^{y+2}(y+2) << d^{y+2}(x,x+1)\) and every \(d(x,n) >> f_{x-1}(n)\) by at least a factor of 3 to 2 for any n.

This is not obvious because comparing the last nested function we get

\(f_{x-1}(y+2) << d(x,x+1)\) in the case y>x+1, the f function dominates and the d(x,) function growth rate may not be fast enough to compensate, especially when y >> x.

Proof

Let \(f_{x-1}^r(y) >> d^r(x,x+1)\) be any case where the f function is dominating the d function. When this is true then because the d(x,) function growth rate dominates, then it must be true that \(f_{x-1}(y) >> d(x,x+1)\) and:

\(f_{x-1}(y) = d(x,x+1) + a_0\)

\(d(x,n) >> f_{x-1}(n)\) by a minimum of a factor of 3 to 2, so if \(f_{x-1}^2(y) >> d^2(x,x+1)\) then \(a_0\) must have a minimum size.

\(2.f_{x-1}(y) = 2.(d(x,x+1) + a_0) >> 3.d(x,x+1)\) so \(a_0 >> 3.d(x,x+1)/2\) lets assume \(a_0 = 3.d(x,x+1)/2 + a_1\)

At this point we have prooved that if r>=2 then y will be >=r. Lets calculate some trivial examples:

\(f_0(y) = d(1,2) + a_0 = d(1,2) + 3.d(1,2)/2 + a_1 >> 5.d(1,2)/2 = 5*5/2 = 12.5\) so \(y >> 11\)

\(f_1(y) = d(2,3) + a_0 = d(2,3) + 3.d(2,3)/2 + a_1 >> 5.d(2,3)/2 = 5*17/2 = 42.5\) so \(y >> 3\)

and in all other cases y>x+1 from the comparison rule, so y>3.

But how big must \(a_1\) be for r=3 such as \(f_{x-1}^3(y) >> d^3(x,x+1)\).

\(2.2.f_{x-1}(y) = 4.(d(x,x+1) + a_0) = 4.(d(x,x+1) + 3.d(x,x+1)/2 + a_1) = 7.d(x,x+1) + 4.a_1) >> 3.3.d(x,x+1)\)

and \(7.d(x,x+1) + 4.a_1) >> 9.d(x,x+1)\) so \(a_1 >> d(x,x+1)/2\)

lets assume \(a_1 = d(x,x+1)/2 + a_2\) and \(a_0 = 2.d(x,x+1) + a_2)\) and lets calculate:

\(f_2(y) = d(3,4) + a_0 = d(3,4) + 2.d(3,4) + a_2 >> 3.d(3,4) = 3*5099 = 15297\) so \(y >> 10\)

and in all other cases y>x+1 from the comparison rule, so y>6.

Completion of Proof

This proof by induction shows that each iteration of calculating \(a_n\) for r>=4 will require the minimum bound for y to increase by >=1 every time. Which means the requirement that y>=r must change to y>r and:

\(f_x(y+2) << d(x+1,y)\) for all cases including any examples of \(f_{x-1}^r(y) >> d^r(x,x+1)\)

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.