10,828 Pages

## 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:

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)$$

$$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)$$