10,835 Pages

## Growth Rate of the S Function

This blog will provide a detailed calculation and references for the growth rate of The S Function that I have developed. The growth rate is comparable to:

$$S(n,T^{T(0)}(0),1) \approx f_{\varphi(1,1,0)}(n)$$

## Introduction

The S function is recursively defined set of two functions $$S()$$ and $$T()$$ which use string substitution procedures only. S Functions can be either restricted or generalised. Refer to my main blog on The S Function for a full definition of how the function is constructed.

As a simple introduction it will be useful to compare a typical S function with more familiar functions:

$$S(3,2,1) = f_2(3)$$ ordinal value

This equivalence is intentional. In fact:

$$S(n,g,h) = f_g^h(n)$$ ordinal value

This equivalence will become more obvious if you refer to the definitions and rules for the function. I have intentionally defined The S Function to be a string substitution function with no explicit mathematical (e.g. algebraic) connotations. However the above equivalences will re-occur throughout the calculations. It is based on the definition that all restricted $$S()$$ functions belong to a well-ordered sequence and every individual restricted $$S()$$ function will have an assigned ordinal value equivalent to the result of the equivalent FGH function. In the case above; $$S(3,2,1)$$ has the ordinal value 24.

The $$T()$$ function can be compared to various ordinals.

$$T(0) == \omega$$ The similarity is intentional.

The generalised S Functions, the functions of the form $$S(T(0),g,h)$$, are similar to the ordinals that arise from the various attempts to define an FGH of Omega function, therefore:

$$S(T(0),0,1) == \omega + 1$$

$$S(T(0),1,1) == \omega.2$$

The similarities are intentional. However, the similarity fades as we examine larger and larger inputs to the $$T()$$ function.

We can now start calculating the Growth Rate of the restricted S Function.

## Summary of Growth Rate Calculations

Here is a summary of the Growth Rate Calculations that are explained in more detail in the following sections:

$$S(n,T(0),1) = f_{\omega}(n)$$

$$S(n,S(T(0),0,1),1) = f_{\omega + 1}(n)$$

$$S(n,S(T(0),1,1),1) = f_{\omega.2}(n)$$

$$S(n,S(T(0),2,1),1) > f_{\omega^2}(n)$$

$$S(n,S(T(0),2,2),1) > f_{\omega\uparrow\uparrow 2}(n)$$

$$S(n,S(T(0),3,1),1) > f_{\omega\uparrow\uparrow n}(n) = f_{\varphi(1,0)}(n) = f_{\epsilon_0}(n) = f_{\psi(0)}(n)$$

$$S(n,S(T(0),4,1),1) > f_{\varphi(2,0)}(n) = f_{\zeta_0}(n) = f_{\psi(\Omega)}(n)$$

$$S(n,S(T(0),5,1),1) > f_{\varphi(3,0)}(n) = f_{\psi(\Omega^2)}(n)$$

$$S(n,S(T(0),m,1),1) > f_{\varphi(m-2,0)}(n)$$

$$S(n,T(1),1) \approx f_{\varphi(\omega,0)}(n)$$

$$S(n,T(2),1) > f_{\varphi^2(1_*,0)}(n) = f_{\varphi(\varphi(1,0),0)}(n)$$

$$S(n,T(3),1) > f_{\varphi^3(1_*,0)}(n)$$

$$S(n,T(m),1) > f_{\varphi^m(1_*,0)}(n)$$

$$S(n,T(T(0)),1) > f_{\varphi(1,0,0)}(n)$$

$$S(n,T(S(T(0),0,T(0)),1) > f_{\varphi(1,0,1)}(n)$$

$$S(n,T^3(0),1) > f_{\varphi^2(1,0,0_*)}(n)$$

$$S(n,T^m(0),1) > f_{\varphi^{m-1}(1,0,0_*)}(n)$$

$$S(n,T^{T(0)}(0),1) \approx f_{\varphi(1,1,0)}(n)$$

## Summary of General Results

Here is a summary of some general results. Refer to the detailed calculations below for more information:

$$S(n,S(T(0),m,1),1) > f_{\varphi(m-2,0)}(n)$$

$$S(T(0),m,1) > \varphi(m-2,0)$$

$$S(\beta,m,T(0)) > \varphi(m-1,\beta + 1)$$ where $$\beta >= \varphi(m,0)$$

$$S(\beta,m,T(0)) > \varphi(m-1,\gamma + 1)$$ where $$\beta = \varphi(m-1,\gamma)$$

$$S(\beta,m,T(0)) > \varphi(m-1,0)$$ where $$\beta < \varphi(m-1,0)$$

$$S(n,T(m),1) > f_{\varphi^m(1_*,0)}(n)$$

$$T(m + 1) > \varphi(T(m),0)$$

$$T(m) > \varphi^m(1_*,0)$$

$$S(n,T(T(0)),1) > f_{\varphi(1,0,0)}(n)$$

$$T(T(0)) > \varphi(1,0,0)$$

$$S(\beta,T(T(0)),1) > \varphi(1,0,\beta + 1)$$ where $$\beta >= \varphi(1,1,0)$$

$$S(\beta,T(T(0)),1) > \varphi(1,0,\gamma + 1)$$ where $$\beta = \varphi(1,0,\gamma)$$

$$S(\beta,T(T(0)),1) > \varphi(1,0,0)$$ where $$\beta < \varphi(1,0,0)$$

$$T(\beta) \approx \varphi(1,0,\beta + 1)$$ where $$\beta >= \varphi(1,1,0)$$

$$T(\beta) \approx \varphi(1,0,\beta)$$ where $$\beta >= \varphi(1,0,0)$$

## Growth Rate up to $$S(n,T(0),1)$$

All restricted S Functions belong to a well-ordered sequence and every individual restricted $$S()$$ function will have an assigned ordinal value. By definition:

$$S(0,0,0) = 0 = 0$$

$$S(1,0,0) = 1 = 1$$

$$S(n,0,0) = n = n$$

$$S(n,g,h) = f_g^h(n)$$

Therefore the Growth Rate of the S Function up to $$S(n,g,h)$$ where $$g$$ is a finite integer, grows at a rate comparable to $$f_{\omega}^h(n)$$, and no additional proof should be required. In fact:

$$S(n,T(0),1) = f_{\omega}(n)$$

## Growth Rate up to $$S(n,S(T(0),2,2),1)$$

Also refer to the various blogs for an FGH of Omega function to calculate the growth rate of The S Function:

$$S(n,S(T(0),1,1),1) = f_{\omega.2}(n)$$

$$S(n,S(S(T(0),1,1),0,1),1) = f_{\omega.2 + 1}(n)$$

$$S(n,S(S(T(0),1,1),0,T(0)),1) = f_{\omega.2 + n}(n) = f_{\omega.3}(n)$$

$$S(n,S(S(T(0),1,1),0,S(T(0),1,1)),1) = S(n,S(T(0),1,2),1) = f_{\omega.2 + \omega.2}(n) = f_{\omega.4}(n)$$

$$S(n,S(T(0),2,1),1) > f_{\omega.\omega}(n) = f_{\omega^2}(n)$$

and

$$S(n,S(T(0),2,2),1) = S(n,S(S(T(0),2,1),1,S(T(0),2,1)),1) >> f_{\omega^{\omega}}(n)$$

because

$$S(n,S(T(0),2,2),1) > f_{\omega^2.2^{\omega^2}}(n) > f_{\omega^{\omega}}(n)$$

where $$n^2.2^{n^2} > 2^{n^2} = 2^{n.n} = (2^n)^n > n^n$$

## Growth Rate up to $$S(n,S(T(0),3,1),1)$$

From here we can show:

$$S(n,S(T(0),2,3),1) = S(n,S(S(T(0),2,2),1,S(T(0),2,2)),1) >> f_{\omega\uparrow\uparrow 3}(n)$$

because

$$n^2.2^{n^2}.2^{n^2.2^{n^2}} > 2^{n^2.2^{n^2}} = 2^{n.n.2^{n.n}} = (2^{n.n})^{(2^n)^n} > n^{(2^n)^n} > n^{n^n} = n\uparrow\uparrow 3$$

then

$$S(n,S(T(0),2,m),1) > f_{\omega\uparrow\uparrow m}(n)$$

$$S(n,S(T(0),2,m + 1),1) > f_{\omega\uparrow\uparrow (m + 1)}(n)$$

until

$$S(n,S(T(0),3,1),1) = S(n,S(T(0),2,T(0)),1) >> f_{\omega\uparrow\uparrow n}(n) = f_{\varphi(1,0)}(n) = f_{\epsilon_0}(n) = f_{\psi(0)}(n)$$

Here are some examples of this equality:

$$S(2,S(T(0),3,1),1) > S(2,S(T(0),1,1),1) = f_{\omega.2}(2) = f_{\omega^2}(2) = f_{\epsilon_0}(2)$$

$$S(3,S(T(0),3,1),1) = S(3,T(1),1) > f_{\varphi(1,0)}(3) = f_{\epsilon_0}(3) = f_{\psi(0)}(3)$$

$$S(4,S(T(0),3,1),1) > f_{\varphi(1,0)}(4) = f_{\epsilon_0}(4) = f_{\psi(0)}(4)$$

## Growth Rate up to $$S(n,S(T(0),4,1),1)$$

$$S(n,S(T(0),3,1),1) > f_{\varphi(1,0)}(n)$$

$$S(n,S(S(T(0),3,1),2,1),1) > f_{\varphi(1,0)^2}(n)$$

then

$$S(S(T(0),3,1),2,1) > \varphi(1,0)^2$$

$$S(S(T(0),3,1),2,2) > \varphi(1,0)\uparrow\uparrow 2$$

$$S(S(T(0),3,1),2,3) > \varphi(1,0)\uparrow\uparrow 3$$

$$S(S(T(0),3,1),2,T(0)) > \varphi(1,1)$$

$$S(S(T(0),3,1),2,S(T(0),1,1)) > \varphi(1,2)$$

$$S(S(T(0),3,1),2,S(T(0),1,2)) > \varphi(1,4)$$

$$S(S(T(0),3,1),2,S(T(0),2,1)) > \varphi(1,\omega^2)$$

$$S(T(0),3,2) = S(S(T(0),3,1),2,S(T(0),3,1)) > \varphi(1,\varphi(1,0))$$

$$S(S(T(0),3,2),2,T(0)) > \varphi(1,\varphi(1,0) + 1)$$

$$S(S(T(0),3,2),2,S(T(0),2,1)) > \varphi(1,\varphi(1,0) + \omega^2)$$

$$S(S(T(0),3,2),2,S(T(0),3,1)) > \varphi(1,\varphi(1,0) + \varphi(1,0))$$

$$S(T(0),3,3) = S(S(T(0),3,2),2,S(T(0),3,2)) > \varphi(1,\varphi(1,0) + \varphi(1,\varphi(1,0)))$$

$$> \varphi(1,\varphi(1,\varphi(1,0))) = \varphi^3(1,0_*)$$

$$S(T(0),4,1) = S(T(0),3,T(0)) > \varphi^{\omega}(1,0_*) = \varphi(2,0)$$

## Growth Rate up to $$S(n,S(T(0),5,1),1)$$

$$S(S(T(0),4,1),2,T(0)) > \varphi(1,\varphi(2,0) + 1)$$

$$S(S(T(0),4,1),2,S(T(0),1,1)) > \varphi(1,\varphi(2,0) + 2)$$

$$S(S(T(0),4,1),2,S(T(0),1,2)) > \varphi(1,\varphi(2,0) + 4)$$

$$S(S(T(0),4,1),2,S(T(0),2,1)) > \varphi(1,\varphi(2,0) + \omega^2)$$

$$S(S(T(0),4,1),2,S(T(0),2,2)) > \varphi(1,\varphi(2,0) + \omega\uparrow\uparrow 2)$$

$$S(S(T(0),4,1),2,S(T(0),3,1)) > \varphi(1,\varphi(2,0) + \varphi(1,0))$$

$$S(S(T(0),4,1),3,1) =$$

$$S(S(T(0),4,1),2,S(T(0),4,1)) > \varphi(1,\varphi(2,0).2)$$

$$S(S(S(T(0),4,1),3,1),2,T(0)) > \varphi(1,\varphi(2,0).2 + 1)$$

$$S(S(S(T(0),4,1),3,1),2,S(T(0),4,1)) > \varphi(1,\varphi(2,0).2 + \varphi(2,0))$$

$$S(S(S(T(0),4,1),3,1),2,S(S(T(0),4,1),2,T(0)) > \varphi(1,\varphi(2,0).2 + \varphi(1,\varphi(2,0) + 1))$$

$$S(S(T(0),4,1),3,2) =$$

$$S(S(S(T(0),4,1),3,1),2,S(S(T(0),4,1),3,1) > \varphi(1,\varphi(2,0).2 + \varphi(1,\varphi(2,0).2))$$

$$> \varphi(1,\varphi(1,\varphi(2,0)+1)) = \varphi^2(1,(\varphi(2,0)+1)_*)$$

$$S(S(T(0),4,1),3,T(0)) = \varphi^{\omega}(1,(\varphi(2,0)+1)_*) = \varphi(2,1)$$

$$S(S(T(0),4,1),3,S(T(0),1,1)) = \varphi(2,2)$$

$$S(S(T(0),4,1),3,S(T(0),1,2)) = \varphi(2,4)$$

$$S(S(T(0),4,1),3,S(T(0),2,1)) = \varphi(2,\omega^2)$$

$$S(S(T(0),4,1),3,S(T(0),3,1)) = \varphi(2,\varphi(1,0))$$

$$S(T(0),4,2) =$$

$$S(S(T(0),4,1),3,S(T(0),4,1)) = \varphi(2,\varphi(2,0)) = \varphi^2(2,0_*)$$

$$S(T(0),5,1) = S(T(0),4,T(0)) = \varphi^{\omega}(2,0_*) = \varphi(3,0)$$

## Growth Rate up to $$S(n,T(1),1)$$

$$T(1) = S(T(0),T(0),1)$$

then

$$S(3,T(1),1) = S(3,S(T(0),T(0),1),1) = S(3,S(T(0),3,1),1) > f_{\epsilon_0}(3) = f_{\varphi(1,0)}(3)$$

$$S(4,T(1),1) = S(4,S(T(0),T(0),1),1) = S(4,S(T(0),4,1),1) > f_{\varphi(2,0)}(4)$$

$$S(5,T(1),1) = S(5,S(T(0),T(0),1),1) = S(5,S(T(0),5,1),1) > f_{\varphi(3,0)}(5)$$

and

$$S(n,T(1),1) > f_{\varphi(n - 2,0)}(n)$$

$$S(n,T(1),1) \approx f_{\varphi(\omega,0)}(n)$$

because

$$S(S(n,T(1),1),S(T(0),3,1),1) > f_{\varphi(1,0)}(f_{\varphi(n - 2,0)}(n))$$

$$S(S(n,T(1),1),S(T(0),n,1),1) > f_{\varphi(n - 2,0)}(f_{\varphi(n - 2,0)}(n)) = f^2_{\varphi(n - 2,0)}(n)$$

$$S(S(n,T(1),1),S(T(0),S(n,0,1),1),1) > f_{\varphi(n - 1,0)}(n + 1)$$

$$S(S(n,T(1),1),S(T(0),S(n,0,2),1),1) > f_{\varphi(n,0)}(n + 2) > f_{\varphi(n,0)}(n) = f_{\varphi(\omega,0)}(n)$$

$$S(S(n,T(1),1),S(T(0),S(n,0,3),1),1) > f_{\varphi(\omega,0)}(n + 1)$$

$$S(S(n,T(1),1),S(T(0),S(n,1,1),1),1) > f_{\varphi(\omega,0)}(n.2)$$

$$S(S(n,T(1),1),S(T(0),S(n,2,1),1),1) > f_{\varphi(\omega,0)}(n^2)$$

$$S(S(n,T(1),1),S(T(0),S(n,3,1),1),1) > f_{\varphi(\omega,0)}(f_3(n))$$

$$S(S(n,T(1),1),S(T(0),S(n,T(0),1),1),1) > f_{\varphi(\omega,0)}(f_{\omega}(n))$$

$$S(S(n,T(1),1),S(T(0),S(n,S(T(0),1,1),1),1),1) > f_{\varphi(\omega,0)}(f_{\omega.2}(n))$$

$$S(S(n,T(1),1),S(T(0),S(n,S(T(0),2,1),1),1),1) > f_{\varphi(\omega,0)}(f_{\omega^2}(n))$$

$$S(S(n,T(1),1),S(T(0),S(n,S(T(0),3,1),1),1),1) > f_{\varphi(\omega,0)}(f_{\varphi(1,0)}(n))$$

$$S(n,T(1),2) = S(S(n,T(1),1),T(1),1) = S(S(n,T(1),1),S(T(0),T(0),1),1) =$$

$$S(S(n,T(1),1),S(T(0),S(n,S(T(0),T(0),1),1),1),1) > f_{\varphi(\omega,0)}(f_{\varphi(n - 2,0)}(n))$$

$$\approx f^2_{\varphi(\omega,0)}(n)$$

$$S(n,S(T(1),0,1),1) = S(n,T(1),n) \approx f^n_{\varphi(\omega,0)}(n) = f_{\varphi(\omega,0) + 1}(n)$$

## Growth Rate up to $$S(n,T(2),1)$$

$$T(2) = S(T(1),T(1),1)$$

then

$$S(T(1),0,1) \approx \varphi(\omega,0) + 1$$

$$S(T(1),1,1) \approx \varphi(\omega,0).2$$

$$S(T(1),2,1) > \varphi(\omega,0)^2$$

$$S(T(1),2,T(0)) > \varphi(1,\varphi(\omega,0) + 1)$$

$$S(T(1),2,S(T(0),1,1)) > \varphi(1,\varphi(\omega,0) + 2)$$

$$S(T(1),2,S(T(0),1,2)) > \varphi(1,\varphi(\omega,0) + 4)$$

$$S(T(1),2,S(T(0),2,1)) > \varphi(1,\varphi(\omega,0) + \omega^2)$$

$$S(T(1),2,S(T(0),3,1)) > \varphi(1,\varphi(\omega,0) + \varphi(1,0))$$

$$S(T(1),3,1) = S(T(1),2,T(1)) =$$

$$S(T(1),2,S(T(0),T(0),1)) \approx \varphi(1,\varphi(\omega,0).2)$$

$$S(S(T(1),3,1),2,T(0)) > \varphi(1,\varphi(\omega,0).2 + 1)$$

$$S(T(1),3,2) =$$

$$S(S(T(1),3,1),2,S(T(1),3,1)) > \varphi(1,\varphi(\omega,0).2 + \varphi(1,\varphi(\omega,0).2))$$

$$> \varphi(1,\varphi(1,\varphi(\omega,0) + 1)) = \varphi^2(1,(\varphi(\omega,0) + 1)_*)$$

$$S(T(1),3,T(0)) > \varphi^{\omega}(1,(\varphi(\omega,0) + 1)_*) = \varphi(2,\varphi(\omega,0) + 1)$$

$$S(T(1),4,T(0)) > \varphi(3,\varphi(\omega,0) + 1)$$

$$S(T(1),T(0),T(0)) \approx \varphi(\omega,1)$$

$$S(T(1),S(T(0),0,1),1) \approx \varphi(\omega + 1,0)$$

$$S(T(1),S(T(0),1,1),1) \approx \varphi(\omega.2,0)$$

$$S(T(1),S(T(0),2,1),1) > \varphi(\omega^2,0)$$

$$S(T(1),S(T(0),3,1),1) > \varphi(\varphi(1,0),0)$$

$$T(2) = S(T(1),T(1),1) =$$

$$S(T(1),S(T(0),T(0),1),1) \approx \varphi(\varphi(\omega,0),0) = \varphi^2(\omega_*,0)$$

## Growth Rate up to $$S(n,T(T(0)),1)$$

$$T(m + 1) = S(T(m),T(m),1)$$

then

$$T(3) = S(T(2),T(2),1) \approx \varphi^3(\omega_*,0)$$

$$T(m) \approx \varphi^m(\omega_*,0)$$

$$T(T(0)) \approx \varphi^{\omega}(\omega_*,0) = \varphi(1,0,0) = \Gamma_0$$

## Growth Rate up to $$S(n,T(S(T(0),0,1)),1)$$

$$S(T(T(0)),3,1) \approx \varphi(1,\Gamma_0 + 1)$$

$$S(T(T(0)),T(0),1) \approx \varphi(\omega,\Gamma_0 + 1)$$

$$S(T(T(0)),S(T(0),1,1),1) \approx \varphi(\omega.2,\Gamma_0 + 1)$$

$$S(T(T(0)),S(T(0),2,1),1) \approx \varphi(\omega^2,\Gamma_0 + 1)$$

$$S(T(T(0)),S(T(0),3,1),1) \approx \varphi(\varphi(1,0),\Gamma_0 + 1)$$

$$S(T(T(0)),T(1),1) \approx \varphi(\varphi(\omega,0),\Gamma_0 + 1)$$

$$S(T(T(0)),T(2),1) \approx \varphi(\varphi^2(\omega_*,0),\Gamma_0 + 1)$$

$$T(S(T(0),0,1)) =$$

$$S(T(T(0)),T(T(0)),1) \approx \varphi(\varphi(1,0,0) + 1,\varphi(1,0,0) + 1)$$

## Growth Rate up to $$S(n,T^3(0),1)$$

$$T(m + 1) > \varphi(T(m),0)$$

$$T(S(T(0),0,2)) > \varphi^2((\varphi(1,0,0) + 1)_*,0)$$

$$T(S(T(0),0,3)) > \varphi^3((\varphi(1,0,0) + 1)_*,0)$$

$$T(S(T(0),1,1)) =$$

$$T(S(T(0),0,T(0)) > \varphi^n((\varphi(1,0,0) + 1)_*,0) = \varphi(1,0,1)$$

$$T(S(T(0),1,2)) > \varphi(1,0,3)$$

$$T(S(T(0),2,1)) > \varphi(1,0,\omega^2)$$

$$T(S(T(0),3,1)) > \varphi(1,0,\varphi(1,0))$$

$$T(T(1)) = T(S(T(0),T(0),1)) \approx \varphi(1,0,\varphi(\omega,0))$$

$$T(\beta) > \varphi(1,0,\beta)$$

$$T(T(2)) > \varphi(1,0,\varphi^2(\omega_*,0))$$

$$T(T(m)) > \varphi(1,0,\varphi^m(\omega_*,0))$$

$$T^3(0) = T(T(T(0))) > \varphi(1,0,\varphi(1,0,0)) = \varphi^2(1,0,0_*)$$

## Growth Rate up to $$S(n,T^{T(0)}(0),1)$$

$$T(\beta) > \varphi(1,0,\beta)$$

$$T^4(0) > \varphi^3(1,0,0_*)$$

$$T^m(0) > \varphi^{m - 1}(1,0,0_*)$$

$$T^{T(0)}(0) \approx \varphi^{\omega}(1,0,0_*) = \varphi(1,1,0)$$

## Alternative Calculations of $$S()$$ Growth Rates

I tried some alternative calculations but have since given up on them. The following blogs are no longer relevant:

## Further References

Further references to relevant blogs can be found here: User:B1mb0w