# Where does this array-based fast-growing function fall in the fast-growing hierarchy, and how does it compare to TREE(n)?

[See below for a clarification edit and progress thus far]

So I have been reading into the "fast-growing hierarchy" of functions, and I devised this (somewhat convoluted) function for generating very large numbers, based on an array (there may be similarities with Bower's Array Notation, but I don't think it is identical).:

(source code in C for this function is given below)

1. $\quad S_{\{0\}} (n) = n \uparrow^{\ n-2} n; \text{ where } S_{\{0\}}(0) = 1, S_{\{0\}}(1) = 2, \text{ and } S_{\{0\}}(2) = 4 \text{.}$
2. $\quad S_{\{k\}} (n) = S_{\{k-1\}}^{n} (n), \text{ where } S_{\{k-1\}} \text{ is nested$n$times.}$
3. $\quad S_{\{ k_1, k_2, \ldots, k_n, 0\}} (n) = S_{\{ k_1, k_2, \ldots, k_n\}} (n) \text{.}$
4. $\quad S_{\{ k_1, k_2, \ldots, k_{n-1}, k_n\}}(n) = S_{\{ k_1, k_2, \ldots, S_{\{ k_1, k_2, \ldots, k_{n-1}, k_n - 1\}}(n), k_n - 1\}}(n) \text{.}$
5. $\quad _{k}S(n) = S_{\{n, n, \ldots, n, n\}} (n), \text{where there are$k$instances of$n$in the array.}$
6. $\quad M(n)=\text{ }_{n}S(n) \text{.}$

As an example, $S_{\{n, 1\}} (4) = S_{\{S_{\{n,0\}}(4),0\}} = S_{\{S_{\{n\}}\}}(4)$

This function $M(n)$ grows quite rapidly, with $M(0) = 1$, $M(1) = 2$, and $M(2) >>$ Graham's Number.

It seems to me that $S_{\{0\}}(n)$ would be analogous to $f_{\omega}$ in the fast-growing hierarchy, and $_{1}S(n)$ would be similar to $f_{\omega 2}$. I think that $_{2}S(n)$ would be similar to $f_{\omega^2}$, and $_{3}S(n)$ to $f_{\omega^{\omega}}$, but I am unsure about $M(n)$ in general.

Is there any way to determine where exactly $M(n)$ lies in the fast-growing hierarchy, or at least an upper and lower bound for it? Also, how does $M(3)$ or $M(M(3))$ compare to $TREE(3)$, where $TREE$ refers to Friedman's TREE sequence (http://googology.wikia.com/wiki/TREE_sequence)?

If it helps, I have created a C-language program which implements this function:

/* An implementation of the fast-growing "M" function */

#include <stdio.h>

/*
An implementation of the hyperoperation sequence (analogous to S0(n)).
*/
int hyp(int n, int a, int b) {
if(n == 0) {return b+1;}
else if(n == 1 && b == 0) {return a;}
else if(n == 2 && b == 0) {return 0;}
else if(n >= 3 && b == 0) {return 1;}
else {return hyp(n-1,a,hyp(n,a,b-1));}
}

/*
An implementation of the "S" function, with an array input
*/
int S(int inputArr[], int n) {
int size = sizeof(inputArr)/sizeof(inputArr[0]);
if(size == 1) {
if(inputArr[0] == 0) {return hyp(n,n,n);}
else {
int counter = 1;
int passArray[]={inputArr[0]-1};
int k = S(passArray,n);
while(counter < n) {
k = S(passArray,k);
counter = counter+1;
}
return k;
}
}
else if(inputArr[size-1] == 0) {
int newArray[size-1];
int f;
for(f = 0; f < size-1; f++) {
newArray[f] = inputArr[f];
}
return S(newArray,n);
}
else {
int newArray[size];
int midArray[size];
int f;
for(f = 0; f < size-2; f++) {
newArray[f] = inputArr[f];
}
for(f = 0; f < size-1; f++) {
midArray[f] = inputArr[f];
}
midArray[size-1] = inputArr[size-1]-1;
newArray[size-1] = inputArr[size-1]-1;
newArray[size-2] = S(midArray,n);
return S(newArray,n);
}
}

/*
The "M" function, based on the "S" function defined above
*/
int M(int n) {
int callArray[n];
int k;
for(k = 0; k < n; k++) {callArray[k] = n;}
return S(callArray,n);
}

int main() {
int n = 0;
int k = M(n);
printf("M(%d) = %d\n",n,k);
n = 1;
k = M(n);
printf("M(%d) = ",n);
printf("%d\n",k);
n = 2;
printf("M(%d) = ",n);
k = M(n);
printf("%d\n",k);
return 0; }


EDIT: Clarification and Progress

I think my original definition for the function may have been difficult to follow and I could very well have made a mistake in specifying it. Here is an example of how I intended it to work, as a clarification: $$S_{3,3,2} (n) = S_{3,S_{3,3,1} (n),1} (n) = S_{3,S_{3,S_{3,0} (n),0} (n),1} (n) = S_{3,S_{3,S_3 (n)} (n), 1} (n) = S_{3, S_{3, S_{3, S_3 (n)} (n)} (n)} (n).$$ As one can see, each term creates a huge number of nestings of the S function in its previous terms, and once the final term reaches zero, the process continues for the previous term (which is now likely a nesting of many S functions, as seen in the example), continuing on until there is only one term left, which would likely be quite large.

• If the function falls approximately as you expect, it cannot compete with TREE(3). This number far surpasses the $\Gamma_0$-level and if I am informed right, the level of TREE(3) is so high that it is not even known where approximately it will fall. – Peter May 27 '18 at 9:09
• If you guessed right, $M(n)$ should have $\epsilon_0$-level – Peter May 27 '18 at 9:11
• Actually, after messing around with the function a bit more, it appears that k S(n) falls approximately at w ^^^...^^^[k up-arrows] 2 in the hierarchy, so M(n) would fall at whatever ordinal w ^^^^....^^^^[w] 2 happens to refer to, and epsilon-naught is only equal to 3S(n) with this premise. Does that make any sense? I have only a rudimentary understanding of this topic and so this theory may be far off. – Sid May 27 '18 at 20:09
• @Peter I think it's much less, there is a "mistake" in definition 4 which means it only looks at the last argument and ignores the previous arguments, so $\{k_1,k_2,\cdots,k_n\}$ can be replaced by $\{n,k_n\}$ with the right encoding.(just track the amount of arguments instead of ignoring them). – fejfo May 27 '18 at 20:12
• @Sid How did you arrive at $_2S(n)\approx f_{\omega^2}(n)$? I found $_2S(n)\approx f_{\omega\cdot2+1}(n)$? – fejfo May 28 '18 at 18:23

## First look

$$S_{\{0\}}(n)\approx f_\omega(n) \\ \Rightarrow S_{\{k\}}(n)\approx f_{\omega+k}(n)$$

## Property: $S_{\{k_1,k_2,…,k_{m-1},k_m\}}(n)=g^{k_m+1}(k_{m-1}) \text{ with } g(x)=S_{\{k_1,k_2,…,x\}}(n)$

$$S_{\{k_1,k_2,…,k_{m-1},k_m\}}(n) \\=S_{\{k_1,k_2,…,X_1,k_m-1\}}(n) \text{ with } X_0=k_{m-1} \text{ and } X_{i+1}=S_{\{k_1,k_2,…,X_i,k_m-1\}}(n) \\=S_{\{k_1,k_2,…,X_2,k_m-2\}}(n) \\=\cdots \\=S_{\{k_1,k_2,…,X_{k_m-1},1\}}(n)\\=S_{\{k_1,k_2,…,X_{k_m}(n)\}}(n) \\=X_{k_m+1} \\=g^{k_m+1}(k_{m-1}) \text{ with } g(x)=S_{\{k_1,k_2,…,x\}}(n)$$

## Proof by induction $S_{\{k_1,k_2,…,k_{m-1},k_m\}}(n)\approx f_{\omega\cdot2+m-1}(k_m+1)$

### Base case: $m=2$

$$S_{\{k_1,k_2\}}(n)=g^{k_2+1}(k_1) \text{ with } g(x)=S_{\{x\}}(n)\approx f_{\omega+x}(n)\approx f_{\omega\cdot2}(x) \\ S_{\{k_1,k_2\}}(n)\approx f^{k_2+1}_{\omega\cdot2}(k_1)\approx f_{\omega\cdot2+1}(k_2+1)$$

### Succesor case: $m+1$

$$S_{\{k_1,k_2,…,k_{m},k_{m+1}\}}(n)=g^{k_{m+1}+1}(k_m) \text{ with } g(x)=S_{\{k_1,k_2,…,x\}}(n)\approx f_{\omega\cdot 2+m-1}(x) \\S_{\{k_1,k_2,…,k_{m},k_{m+1}\}}(n)\approx f^{k_{m+1}+1}_{\omega\cdot 2+m-1}(x)\approx f_{\omega\cdot 2+m}(k_{m+1}+1)$$

## Conclusion

So $M(n)=_nS(n)\approx f_{\omega\cdot2+n-1}(n+1)\approx f_{\omega\cdot3}(n-1)$

This doesn't even come close to the TREE function which outgrows $f_{\vartheta(\Omega^\omega\omega)}(n)$

• I don’t see how S{k1, k2, ..., k_(m-1), k_m} (n) = S{k1, k2, ..., k_(m-1), 1}? When k_m is decreased by one, there is another call to S in the previous k_(m-1) term; when k_m = 2, k_(m-1) ends up being replaced by something like S{...} (S{...} (n)), and was k_m increases, the previous term contains more and more nested calls to S. Perhaps I made a mistake in my specifying the definition, but (correct me if I’m wrong) that replacement you make in your first step doesn’t seem right. Thanks for the help! – Sid May 28 '18 at 4:17
• @Sid It seems like I made a mistake, the edited version should be more formal but I find it strange new approximation is weaker. – fejfo May 28 '18 at 18:20

I concur with fejfo that $M(n) \approx f_{\omega \cdot 3}(n)$.

Letting $g(n) = S_{\{n\}}(n)$, we have $S_{\{n,1\}}(n) = S_{\{S_{\{n\}}(n)\}}(n) < g^2(n)$. Similarly, if $h(n) = S_{\{n,1\}}(n)$ then $S_{\{n,2\}}(n) = S_{\{S_{\{n,1\}}(n),1\}}(n) < h^2(n) < g^4(n)$. In general, $S_{\{n,m\}}(n) < g^{2^m}(n)$, and $S_{\{n,n\}}(n) < g^{2^n}(n)$. Since $g(n) < f_{\omega \cdot 2}(n)$, $S_{\{n,n\}}(n) < f_{\omega \cdot 2 + 1}(2^n)$.

The same thing happens with the third variable - if $g(n) = S_{\{n,n\}}(n)$, then $S_{\{n,n,n\}}(n) < g^{2^n}(n)$, and so $S_{\{n,n,n\}}(n) \approx f_{\omega \cdot 2 + 2}(2^n)$. ($2^n$ is so much more slowly growing than $f_{\omega \cdot 2 + 1}$ that its effect is imperceptible.) More generally, $S_{\{n,n,\ldots,n\}}(n) \approx f_{\omega \cdot 2 + k-1}(2^n)$, where $k$ is the number if $n$'s in the array. So $M(n) < f_{\omega \cdot 3}(n)$.