CITE THIS NOTEBOOK: An Empirical Study - String Rewrite System Reducibility by Leon Zhao. Wolfram Community JAN 13 2023.
This project is aimed at trying to characterize how the starting state of a string rewrite system effects the result at certain time steps. In specific we explore the simplest case of binary strings. The main motivation is to investigate the influence of the initial conditions and rewrite rules in the rewrite system. Evidently, some rules yield behavior more predictable that that yielded by other rules.
Background
Background
Of interest in the winter school project is the idea of multiway systems, where from very simple sets of rules we are able to represent extremely complex behavior. Although the behavior in general is very complicated, because the rule set is so simple we seek out simple patterns across all possible string inputs of fixed length to some string substitution rule. The aim of this project is to empirically study this behavior by using Mathematica to compute the number of paths in the corresponding digraph of the string substitution system. Specifically, in this project we measure the distribution of the first bit for a given string substitution rule
Method
Method
For a given string substitution rule, the goal is to generate a graph for all initial strings of length , then for each vertex in that graph we compute the number of paths from the root to this vertex. Summing across all vertices in all generated graphs, we produce an approximation for the probability. This is mainly done using the built in functions of FindLength, ResourceFunction[“multiway”] and the GeneralUtilities library, which are to curried together to generate and then compute the total number of paths for each . We make good use of some of Mathematica’s more functional aspects through Map and Replace
n
2
n
Implementation
Implementation
MultiwaySystem[Rules_]:=Function[InitialState,ResourceFunction["MultiwaySystem"][Rules,InitialState,StringLength[InitialState],"StatesGraph",GraphLayout->"LayeredDigraphEmbedding"]]GenerateMultiway=MultiwaySystem[{"01"->"1","10"->"0"}]<<GeneralUtilities`M=Map[Graph|->Map[to|->Pair[StringTake[GraphSources[Graph][[1]],1],Length[FindPath[Graph,GraphSources[Graph][[1]],to,Infinity,All]]],Select[VertexList[Graph],#!=GraphSources[Graph]&]],GenerateMultiway/@StringJoin@@@Tuples[{"0","1"},3]]Flatten[M]Select[Flatten[M],#[[1]]=="0"&]Total[Map[x|->x[[2]],Select[Flatten[M],#[[1]]=="0"&]]]GetTotals[L_]:=Pair[Total[Map[x|->x[[2]],Select[Flatten[L],#[[1]]=="0"&]]],Total[Map[x|->x[[2]],Select[Flatten[L],#[[1]]=="1"&]]]]SolveRules[rules_,n_:5]:=GetTotals[Map[Graph|->Map[to|->Pair[StringTake[to,1],Length[FindPath[Graph,GraphSources[Graph][[1]],to,Infinity,All]]],VertexList[Graph]],MultiwaySystem[rules]/@StringJoin@@@Tuples[{"0","1"},n]]]SolveRules[{"01"->"1","10"->"0"}]SolveRules[{"01"->"0","10"->"1"}]SolveRules[{"01"->"0","10"->"0"}]SolveRules[{"01"->"1","10"->"1"}]SolveRules[{"01"->"1","10"->"1","11"->"1","00"->"1"}]SolveRules[{"01"->"1","10"->"0","11"->"1","00"->"0"}]SolveRules[{"01"->"0","10"->"0","11"->"1","00"->"1"}]SolveRules[{"01"->"0","10"->"1","11"->"0","00"->"1"}]SolveRules[{"00"->"1","11"->"1"}]SolveRules[{"01"->"1","11"->"1"}]SolveRules[{"01"->"1","11"->"0"}]SolveRules[{"10"->"1","00"->"1"},3]SolveRules[{"10"->"1","00"->"1"},4]SolveRules[{"10"->"1","00"->"1"},5]G=MultiwaySystem[{"10"->"1","00"->"1"}]/@StringJoin@@@Tuples[{"0","1"},5]
Results
Results
Rule | Probability of 0 as first bit | Probability of 1 as first bit |
{000,010,100,110} | 0.83 | 0.17 |
{000,010,100,111} | 0.80 | 0.20 |
{000,010,100} | 0.80 | 0.20 |
{000,010,101,110} | 0.75 | 0.25 |
{000,010,101,111} | 0.50 | 0.50 |
{000,010,101} | 0.70 | 0.30 |
{000,010,110} | 0.82 | 0.18 |
{000,010,111} | 0.67 | 0.33 |
{000,010} | 0.74 | 0.26 |
{000,011,100,110} | 0.67 | 0.33 |
{000,011,100,111} | 0.59 | 0.41 |
{000,011,100} | 0.59 | 0.41 |
{000,011,101,110} | 0.35 | 0.65 |
{000,011,101,111} | 0.20 | 0.80 |
{000,011,101} | 0.29 | 0.71 |
{000,011,110} | 0.50 | 0.50 |
{000,011,111} | 0.22 | 0.78 |
{000,011} | 0.30 | 0.70 |
{000,100,110} | 0.82 | 0.18 |
{000,100,111} | 0.78 | 0.22 |
{000,100} | 0.79 | 0.21 |
{000,101,110} | 0.66 | 0.34 |
{000,101,111} | 0.33 | 0.67 |
{000,101} | 0.50 | 0.50 |
{000,110} | 0.74 | 0.26 |
{000,111} | 0.50 | 0.50 |
{000} | 0.65 | 0.35 |
{001,010,100,110} | 0.61 | 0.39 |
{001,010,100,111} | 0.50 | 0.50 |
{001,010,100} | 0.73 | 0.27 |
{001,010,101,110} | 0.50 | 0.50 |
{001,010,101,111} | 0.25 | 0.75 |
{001,010,101} | 0.41 | 0.59 |
{001,010,110} | 0.57 | 0.43 |
{001,010,111} | 0.34 | 0.66 |
{001,010} | 0.50 | 0.50 |
{001,011,100,110} | 0.50 | 0.50 |
{001,011,100,111} | 0.33 | 0.67 |
{001,011,100} | 0.41 | 0.59 |
{001,011,101,110} | 0.39 | 0.61 |
{001,011,101,111} | 0.17 | 0.83 |
{001,011,101} | 0.23 | 0.77 |
{001,011,110} | 0.41 | 0.59 |
{001,011,111} | 0.18 | 0.82 |
{001,011} | 0.25 | 0.75 |
{001,100,110} | 0.75 | 0.25 |
{001,100,111} | 0.44 | 0.56 |
{001,100} | 0.50 | 0.50 |
{001,101,110} | 0.43 | 0.57 |
{001,101,111} | 0.18 | 0.82 |
{001,101} | 0.25 | 0.75 |
{001,110} | 0.50 | 0.50 |
{001,111} | 0.26 | 0.74 |
{001} | 0.32 | 0.68 |
{010,100,110} | 0.77 | 0.23 |
{010,100,111} | 0.71 | 0.29 |
{010,100} | 0.73 | 0.27 |
{010,101,110} | 0.50 | 0.50 |
{010,101,111} | 0.30 | 0.70 |
{010,101} | 0.50 | 0.50 |
{010,110} | 0.68 | 0.32 |
{010,111} | 0.50 | 0.50 |
{010} | 0.72 | 0.28 |
{011,100,110} | 0.59 | 0.41 |
{011,100,111} | 0.41 | 0.59 |
{011,100} | 0.50 | 0.50 |
{011,101,110} | 0.43 | 0.57 |
{011,101,111} | 0.20 | 0.80 |
{011,101} | 0.27 | 0.73 |
{011,110} | 0.28 | 0.72 |
{011,111} | 0.21 | 0.79 |
{011} | 0.28 | 0.72 |
{100,110} | 0.75 | 0.25 |
{100,111} | 0.70 | 0.30 |
{100} | 0.72 | 0.28 |
{101,110} | 0.50 | 0.50 |
{101,111} | 0.21 | 0.79 |
{101} | 0.28 | 0.72 |
{110} | 0.68 | 0.32 |
{111} | 0.35 | 0.65 |
Trivia & Insights
Trivia & Insights
Future Work
Future Work
For the current problem, the trivia should be explored a little bit more to see if there’s any interesting insights to the appearance of Stirling Numbers. Additionally, the current approximation of probability has everything assumed to be independent, which is not the case in reality. If instead of considering the entire graph, we consider across a certain number of time steps or distance from the root of the graph, then we will regain independence. Additionally we should check correspondences between certain indices, for instance it’s possible the middle portion of a string having more ones correlates to having more ones at the start of the ending string for any particular rule.
To extend the project we may try non-binary strings as well. In the case of binary strings, a brute force evaluation is efficient on small enough strings. If we were to apply this to longer strings as well as more complex replacement rules, then either a faster evaluation algorithm for counting paths should be designed, or a robust method of approximating across different strings with some corresponding error approximation.
To extend the project we may try non-binary strings as well. In the case of binary strings, a brute force evaluation is efficient on small enough strings. If we were to apply this to longer strings as well as more complex replacement rules, then either a faster evaluation algorithm for counting paths should be designed, or a robust method of approximating across different strings with some corresponding error approximation.