[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 at 9:09
  • If you guessed right, $M(n)$ should have $\epsilon_0$-level – Peter May 27 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 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 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 at 18:23
up vote 1 down vote accepted

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

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.