10,821 Pages

## 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