FANDOM


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

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.