The S Function (substitution function) Version 2
The S function offers a way to generate very large string sequences (representing large numbers). The function grows at the rate \(f_{\varphi(1,1,0)}(n)\) .
Refer to my The Alpha Function blogs for more information on my work.
This blog is a significant update to the original Version 1 of this function. Please keep this in mind if you refer to the earlier blog.
What is the S Function
The S function is recursively defined set of two functions \(S()\) and \(T()\) which use string substitution procedures only. They do not explicitly use any mathematical or transfinite ordinal theory. The String substitution procedures have been converted into a program. Refer to my blogs on The Alpha Function for more information and presentation of the results.
The S function is defined recursively as follows:
\(S(a,b,c)\) where \(a,b,c\) can be finite integer \(n\), an \(S()\) function or a \(T()\) function
\(T(d)\) where \(d\) can be finite integer \(n\), an \(S()\) function or a \(T()\) function
There is one initial rule that applies to \(S()\) which is:
\(S(a,b,0) = a\) for any \(b\)
Definition of the S Function
An arbitrary \(S()\) function, lets call it \(s_m\), is constructed using induction as follows:
- \(s_0 = S(a_0,b_0,c_0 < a_0)\)
- \(s_{i+1} = S(s_0,b_{i+1} < b_i,c_{i+1} < s_i)\), and
- if \(b_i>0\) then \(0 < c_i\) for any \(i\)
Restricted S Functions
Any arbitrary \(S()\) function is either restricted or generalised. A restricted \(S()\) function has these additional constraints:
- \(a_0\) is any finite integer \(n\)
- \(b_0\) is any generalised \(S()\) function
As explained later in this blog, only restricted \(S()\) functions are translated (mapped) to large finite ordinals.
Here is a worked example:
- Let \(a_0 = 3\)
- Let \(b_0 =\) generalised S function. See next section but for now lets call this \(B\).
- Let \(c_0 = 1\) or \(2\). It can also be \(0\) but only if \(b_0 = 0\). Lets choose \(2\)
- Then \(s_0 = S(3,B,2)\)
- Let \(b_1 = 0\) assuming \(B > 0\)
- Let \(0 <= c_1 < S(3,B,2)\). Lets choose \(1\)
- Then \(s_m = s_1 = S(S(3,B,2),0,1)\). The construction completes because \(b_1 = 0\) and \(b_2 < b_1\) would require negative values which are not allowed.
Of course, \(c_1 = 1\) is a trivial example. It could be any S function up to \(S(3,B,2)\) which could be constructed in a recursive way provided the resulting S function is smaller using the Ordering \(<\) procedure described in a section below.
You will find that any S function beginning with the values \(a_0 < 3\) or \(b_0 < B\) or \(c_0 < 2\) will result in a smaller S function. This will be true regardless of the number of inductive steps taken to construct \(c_1\).
Generalised S Functions
A generalised \(S()\) function has these alternative constraints:
- \(a_0\) is any finite integer \(n\) or any \(T()\) function
- \(b_0 < a_0\)
Here is a worked example:
- Let \(a_0 = T(p)\)
- \(p\) can be any generalised S Function but lets choose \(p=2\)
- Let \(b_0 < T(2)\)
- Lets choose \(b_0 = S(T(1),0,1)\)
- Let \(c_0 < T(2)\)
- Lets choose \(c_0 = 3\)
- Let \(b_1 = 0\)
- Let \(0 <= c_1 < S(T(2),S(T(1),0,1),3)\). Lets choose \(c=2\)
- Then \(s_m = s_1 = S(S(T(2),S(T(1),0,1),3),0,2)\). The construction completes because \(b_1 = 0\) and \(b_2 < b_1\) would require negative values which are not allowed.
We can complete the worked example from the previous section as follows:
- \(s_m = S(S(3,B,2),0,1)\)
- \(B = S(S(T(2),S(T(1),0,1),3),0,2)\)
- \(s_m = S(S(3,S(S(T(2),S(T(1),0,1),3),0,2),2),0,1)\)
Equivalence (=) and Ordering (<)
\(S()\) functions can be equivalent (=) or in an ascending order (<). These can be evaluated for two arbitrary S functions: \(U(), V()\) using the two string substitution procedures:
\(sub()\)
\(dec()\)
\(U() = V()\) are equivalent only if there exists:
\(∃ z\) such that string \(sub^z(U())\) is identical to string \(V()\)
\(U() < V()\) are in ascending order only if there exists:
\(∃ z\) such that string \(U()\) is identical to string \(dec^z(V())\)
\(T()\) functions can be equivalent (=) or in an ascending order (<), simply, as follows:
\(T(x) = T(y)\) if and only if \(x = y\)
\(T(x) < T(y)\) if and only if \(x < y\)
sub() String Substitution Procedure
The S function only uses string substitution. Substitutions can occur using one of two procedures:
sub()
dec()
Rule-set for the sub() procedure: The sub() procedure performs string substitutions on one S Function, resulting in equivalent S Functions. For any arbitrary S Function \(S(a,b,c)\):
\(c\) | \(b\) | \(sub(S(a,b,c))\) |
---|---|---|
\(T()\) | any | \(= S(a,b,sub(c))\) |
\(1\) | \(T()\) | \(= S(a,sub(b),1)\) |
\(0\) | \(= S(a,0,1)\) | |
else | \(= S(a,dec(b),a)\) | |
else | any | \(= S(S(a,b,dec(c)),b,1)\) |
Rule-set for the sub() procedure applied to T functions will usually result in an equivalent S Function. For any arbitrary T Function \(T(d)\) appearing in an arbitrary S function \(S(a,b,c)\), then lets call parameter \(a\), the parent of \(b,c\) and hence \(T(d)\):
parent \(a\) | \(d\) | \(sub(T(d))\) |
---|---|---|
Generalised \(S()\) | any | \(= sub(T(d))\) but use the parent of \(a\) instead. |
Restricted \(S()\) | \(T()\) | \(= T(sub(d))\) |
\(0\) | \(= a\) | |
else | \(= S(T(dec(d)),T(dec(d)),1)\) |
dec() String Substitution Procedure
For any arbitrary S Function \(S()\), the dec() procedure involves two steps:
1. Recursively apply the sub() procedure on \(S()\) until:
\(S() = sub^{z}(S()) = S(S_i(),0,m)\)
2. Decrement \(m\) by 1:
\(dec(S()) = dec(sub^{z}(S())) = dec(S(S_i(),0,m))\)
- \(= S(S_i(),0,dec(m))\) when \(m\) is an S Function, or
- \(= S(S_i(),0,m - 1)\) when \(m\) is a finite integer.
Some Example S Functions
Here are some examples of restricted S Functions in ascending order:
\(0\)
\(1\)
\(2\)
\(3\)
\(S(3,0,1)\)
\(S(3,0,2)\)
\(S(3,1,1)\)
\(S(S(3,1,1),0,1)\)
\(S(S(3,1,1),0,2)\)
\(S(S(3,1,1),0,S(3,0,1))\)
\(S(3,1,2)\)
\(S(3,2,1)\)
\(S(3,T(0),1)\)
\(S(3,T(0),2)\)
\(S(3,S(T(0),0,1),1)\)
\(S(3,S(T(0),0,1),2)\)
\(S(3,S(T(0),0,2),1)\)
\(S(3,S(T(0),1,1),1)\)
\(S(3,S(T(0),1,2),1)\)
\(S(3,S(T(0),2,1),1)\)
\(S(3,S(T(0),2,2),1)\)
\(S(3,T(1),1)\)
\(S(3,S(T(1),0,1),1)\)
\(S(3,S(T(1),0,2),1)\)
\(S(3,S(T(1),0,T(0)),1)\)
Growth Rate of the S Function
The number of restricted S Function sequences that can be constructed has a growth rate of \(f_{\varphi(1,1,0)}(n)\) . Here are the growth rates for the ordinal values of restricted S Function sequences as they will appear in a well-ordered sequence. Refer to my detailed blog Growth Rate of the S Function for all calculations and further references.
\(S(n,S(T(0),3,1),1) > f_{\varphi(1,0)}(n) = f_{\epsilon_0}(n)\)
\(S(n,T(1),1) > 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(m),1) > f_{\varphi^m(1_*,0)}(n)\)
\(S(n,T(T(0)),1) > f_{\varphi(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)\)
Further References
Further references to relevant blogs can be found here: User:B1mb0w