The S Function (substitution function)

I have written a Version 2 of this function that generalises the function and significantly increases its growth rate. Please refer to that version instead.

The S function offers a way to generate very large string sequences (representing large numbers) which grows at a faster rate than \(f_{SVO}(n)\), and may be possible to extend its range to grow at a comparable rate to Ordinal Collapsing Functions.

Refer to my The Alpha Function blogs for more information on my work.

What is the S Function

The S function is a string substitution function, and does not explicitly use any mathematical or transfinite ordinal theory. It is effectively a computer algorithm that can be converted to a program. My next version of my Alpha Function will do this and present the results.

The S function is defined recursively as follows:

\(S_b^c(a)\) where \(a,b,c\) are S functions

Definition of the S Function

Starting with:

\(S_b^c(a)\) where \(a,b,c\) are S functions

We define a valid S function recursively as \(a_m\) where:

\(a_0 = S_{b_0 = d_p}^{c_o < n}(n)\)

  • and
  • \(d_0 = S_{b_0 < h_q}^{c_o < k_r}(n\) or \(s_n)\)
    • where
    • \(h_q\) is a valid S function with this additional restriction that it uses either:
      • \(n\)
      • smaller subscript \(n\) in \(s_n\) than that used in \(d_0\)
    • \(k_r\) is a valid S function with this additional restriction \(c_0 = 0\)
  • then \(a_n\) and \(d_m\) can be constructed using this substitution procedure on \(j_n\):
    • \(j_{n+1} = S_{b_{n+1} < b_n}^{c_{n+1} < j_n}(j_n)\)

Note that \(d_0\) and \(d_p\) are not valid S functions. Therefore a valid S function \(a_m\) will never be equivalent to \(d_0\) or \(d_p\).

However \(d_0\) and \(d_p\) are valid components of a valid S function. Therefore they will appear inside a valid S function \(a_m\).

Any S Function of the form (\(c = 0)\) collapses to:

\(S_b^0(a) = a\)

The S Function is familiar with but not identical to FGH Functions.

Definition of the wildcard character \(s_n\)

A wildcard character \(s_n\) is used to enable further string substitutions in the S Function. There is a hierarchy of \(s_n\) substitution wildcards, starting with \(s_0\). Typically \(s_0\) is substituted for a finite number \(n\).

The role of \(s_0\) substitution wildcard, is similar to the role of \(\omega\) in FGH functions.

An Example of an S Function

An example of a valid S Function \(a_m\) is:

  • Let \(m = 0, n = 3, b_0 = d_0, c_0 = 1\)

\(a_m = a_0 = S_{d_0}^{1}(3) = S_{d_0}(3)\)

  • Where
  • \(d_0 = S_{b_0 < h_q}^{c_o < k_r}(n\) or \(s_n)\)
  • Let
  • \(n = 0, b_0 = h_0, c_0 = k_0\)

\(a_m = S_{S_{h_0}^{k_0}(s_0)}(3)\)

  • Where
  • \(h_0\) is a valid S function with this additional restriction that it uses either:
    • \(n\)
    • smaller subscript \(n\) in \(s_n\) than that used in \(d_0\)
  • Let
  • \(n = 5, c_0 = 0\)

\(a_m = S_{S_{5}^{k_0}(s_0)}(3)\)

  • Where
  • \(k_0\) is a valid S function with this additional restriction \(c_0 = 0\)
  • Let
  • \(n = 1\)

\(a_m = S_{S_{5}^{1}(s_0)}(3) = S_{S_{5}(s_0)}(3)\)

It will be shown later in this blog that the number of valid S Functions that can be constructed up to this example is greater than \(f_{\zeta_0}(3)\).

String Substitution Rule-Set

The S function only uses string substitution. Substitutions can occur using one of two functions (or substitution algorithms):



Rule-set for the Sub() Algorithm: The Sub() algorithm performs string substitutions on one S Function, resulting in equivalent S Functions. For any arbitrary S Function \(S_b^c(a)\) where \(c,b,a\) are any S Functions:

\(c\) \(b\) \(Sub(S_b^c(a))\)
\(s_{n>0}\) any \(= S_b^{Sub(c)}(a)\)
\(s_0\) any \(= S_b^a(a)\)
\(1\) \(s_{n>0}\) \(= S_{Sub(b)}(a)\)
\(s_0\) \(= S_a(a)\)
\(S()\) \(= S_{Dec(b)}(a)\)
\(S()\) any \(= S_{Sub(b)}(S_b^{Dec(c)}(a))\)

Rule-set for the Dec() Algorithm: For any arbitrary S Function \(S()\), the Dec() algorithm involves two steps:

1. Recursively apply the Sub() function on \(S()\) until:

\(S() = Sub^{z}(S()) = S_0^{m}(S_b^c(a))\)

2. Decrement \(m\) by 1:

\(Dec(S()) = Dec(Sub^{z}(S())) = S_0^{m'}(S_b^c(a))\) where

\(m' = Dec(m)\) when \(m\) is an S Function or \(m' = m - 1\) when \(m\) is a finite integer.

Rule-set for applying Sub() Algorithm to \(s_{n>0}\) substitution wildcards: The Rule-set for Sub() explains how \(s_0\) wildcards are substituted. The rule-set is extended for all other wildcards as follows:

\(Sub(s_{n>0}) = S_{S_{n}^2(s_{n-1}}(s_{n-1})\)

Growth Rate of the S Function


The number of valid S Function sequences that can be constructed has a growth rate faster than \(f_{SVO}(n)\). Here are the growth rates for sub-sets of valid S Function sequences:

\(S_{s_1}(n) >> f_{\varphi(\omega,0)}(n)\)

\(S_{S_3^2(s_0)}(n) >> f_{\varphi(1,0)}(n) = f_{\epsilon_0}(n)\)

\(S_{S_5(s_0)}(n) >> f_{\varphi(2,0)}(n) = f_{\zeta_0}(n)\)

\(S_{s_1}(n) >> f_{\varphi(\omega,0)}(n)\)

\(S_{s_2}(n) >> f_{\varphi(1,0,0)}(n) = f_{\Gamma_0}(n)\)

\(S_{s_m}(n) >> f_{\varphi(1,0_{[m]})}(n)\)

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.