The Ruliad is a relatively new construct proposed by Stephen Wolfram that encompasses all possible trajectories of computation and their relationships with the physical world (i.e. infinite rules, infinite initial conditions, and infinite time). In this sense, it is intricately linked to the structure and interconnectedness of the universe, and we as a bounded observer within the Ruliad, are only able to experience it narrowly from it inside. Because it is impossible to fully realize the Ruliad, this project seeks to explore a small sliver of it by limiting ourselves to 1 initial state and 2 rules, which still yield an extremely complex and potentially computationally irreducible structure. In particular, this article deals with the numerical system with initial state 1 and rules n2n+1, n3n+1 by examining the behavior of the mergers in the multiway graph. To do this, the article first discretely characterizes them using number theoretical techniques and later examines the causal graph to quantify the complexity of the structure of the states graph. The article then uses entropy to measure the irregularity of the paths to the mergers. Finally, it also examines the multiway function’s application to Push Down Automata.

Introduction

What is a multiway system? A multiway system is formally defined as "a state substitution system in which multiple states are permitted at any stage." In simple terms, this means that given a starting state, we take it and replace it according to a specified set of rules (in our case, the rules are
n2n+1andn3n+1
). We then successively apply our rules, resulting in a tree-like structure, with each possibility branching out into multiple new ones.
Although there exist many types of multiway systems, we'll mainly be dealing with numerical ones in this article. For a general numerical multiway system, the substitution looks something like this:
n{
f
1
[n],
f
2
[n],
f
3
[n],...,
f
n
[n]}
And for a binary substitution system, the rule looks something like this:
n{
f
1
[n],
f
2
[n]},
which yields the following multiway state graph:
Out[]=
Taken from Stephen Wolfram's "Multicomputation with Numbers: The Case of Simple Multiway Systems."
Now what does the multiway state graph of the rule
n{2n+1,3n+1}
look like? Well, for the first few iterations it starts off like so:
Out[]=
But as we run the multiway system for a few more iterations, we get something that looks like this:
Out[]=
State labels removed for better clarity of the image.
Note how at the two green vertices (which represent the numbers 31 and 175), we see
2
separate branches of the tree merge together. We call these points a merger. In fact, running the multiway system for more layers gives:
Out[]=
Generally, the structure of the multiway graph for the rule
n{2n+1,3n+1}
consists of leaf-like branches occasionally joined by a loop (see the image above). It's important to note that each of these loops is caused by a merger. So in essence, the mergers "create" loops. These loops, however, are not of constant size and seem to appear randomly, so the rest of the article attempts to characterize properties of such mergers, providing insight to when and where these loops occur. And it turns out that the simplicity of the rules may very well be the reason such a complex structure emerges.

Discretely Characterizing Mergers

This section seeks to determine properties of where mergers do and do not occur through discrete number theoretical techniques, it also utilizes empirical data to form conjectures (which I did not have enough time to fully prove *yet*).
When initially attempting to characterize the mergers, it makes sense to examine the shape of the multiway graph in order to identify regularity. Purely looking at the structure of the multiway graph, however, does not seem to yield any observable patterns, so we attempt to mathematically determine where the mergers occur. In order to streamline the process, we first define some terms:
◼
  • We let
    r(x)2x+1
    and
    b(x)3x+1
    ,
    (the red edges on the multiway graph denote an operation 2x+1 and the blue edges on the multiway graph denote an operation 3x+1).
    • ◼
  • A merger is a number where two separate paths of the multiway system intersect.
    • ◼
  • A loop is the combined left hand path (LHP) and right hand path (RHP) to a merger. We define the LHP and RHP is such a way that their respective lists of vertices contain precisely two intersections (the start state and end state).
    • Other properties (most notably Confluence and Causal Invariance) will be defined at the start of later sections.

    Properties:

    First of all, we prove that the LHP operations of a merger and the RHP operations of a merger generate strictly 1 or ∞ many merger loops. Basically, the two highlighted paths (see below) either generate a merger once or infinitely many times.
    Out[]=
    To show this, we let the operations on the left hand path (LHP) be
    {
    f
    0
    ,
    f
    1
    ,
    f
    2
    ,…,
    f
    n
    }
    and the operations on the right hand path (RHP) be
    {
    g
    0
    ,
    g
    1
    ,
    g
    2
    ,…,
    g
    m
    }
    with
    f
    i
    ∈{r,b}∀0<=i<=n
    and
    g
    i
    ∈{r,b}∀0<=i<=m.
    So evaluating the functions on the LHP gives
    f
    0
    (
    f
    1
    (
    f
    2
    (…(
    f
    n
    (x))…)))=
    m
    1
    x+
    b
    1
    for some constant integers
    m
    1
    and
    b
    1
    .
    Similarly, evaluating the functions on the RHP gives
    g
    0
    (
    g
    1
    (
    g
    2
    (…(
    g
    n
    (x))…)))=
    m
    2
    x+
    b
    2
    . Since both
    m
    1
    x+
    b
    1
    and
    m
    2
    x+
    b
    2
    are linear functions and we know that they already intersect once, (they generate a merger for some value x), we can conclude that these lines will intersect strictly once or infinitely many times. Thus our statement is proven.
    ​
    An interesting follow up (which is nontrivial to solve), however, is that if the two linear functions intersect infinitely many times (concurrent), then we have that any state of the graph will spawn a merger because the two sets of functions are equal for all initial splitting values
    x
    . But as running the multiway system up to 15 evolutions does not show a loop spawning from every vertex when we delete the leaves (see below), it seems as though a vertex is able to spawn a loop if and only if there exists two unique linear functions generated from our rules
    r(x)2x+1
    and
    b(x)3x+1
    that evaluate to the same thing for that specific vertex value. (This is mentioned later when we analyze the causal graphs).
    Out[]=
    The left image is what the multiway system looks like for 15 evolutions, and the right image is what the multiway system looks like for 15 evolutions with the leaves removed. The code has been adapted from Stephen Wolfram's article "Multicomputation with Numbers: The Case of Simple Multiway Systems."
    Although it seems as though the above property is true, it could also be that the system has not been run for enough evolutions yet. One example of such a case where a certain pattern is not revealed until we run it for long enough time is the rule n↦{n+5,n+7} (we arbitrarily choose 5 and 7 but any 2 integers would work), which looks like the only mergers come from the associative properties of addition for the first few evolutions:
    Out[]=
    However, as Stephen mentions in his article "Multicomputation with Numbers: The Case of Simple Multiway Systems," if we run the system for a few more evolutions, we'll start to see mergers coming from the property that
    LCM[5,7]=35:
    Out[]=
    The key difference between these two rules, however, is that the properties of addition that would lead to mergers are much more obvious than the properties of a combined multiplication and addition function.
    So basically no loops starting from state 1 like this can exist:
    Another thing to look at would be if mergers can be generated by loops with the number of operations on the RHP equal to the number of operations on the LHP. We can start by empirically verifying this.

    Examining the Causal graph of the multiway system

    This section aims to look at the multiway system through another lenses: its Causal graph. The section will introduce the idea of a causal graph and also give an intuition as to why explicitly determining where the mergers occur is so difficult by relating it to a similar multiway system involving string replacement.
    What is the causal graph of a multiway system? Formally defined, "a multiway causal graph gives the causal relationships between all events that can happen on any branch." The idea is to basically take all the edges of a multiway graph, which represent operations that lead to state changes, and then relate them to each other by seeing which operations cause, or depend on, what other operations. Below is a visualization of how one would effectively "translate" between a multiway and causal graph for a simple string substitution system "A"→"AB" with a starting condition of "AA." The states with a blue background come from the multiway graph, and the states with a yellow background come from the causal graph. The graph in the middle illustrates how one would evolve a causal graph from a multiway graph.
    It's important to notice that two transitions in the causal graph are only connected if they directly affect each other. Meaning that two nodes in a causal graph are only connected only if the successive transition would not be possible without the preceding transition. Consider the string replacement causal relation below:
    ◼
  • Causal Invariance: a property of multiway graphs where all possible paths yield the isomorphic causal graphs. Most importantly to us, when causal invariance exists, every branch in the multiway system must eventually merge.
    • ◼
  • Confluence: A simplified form of causal invariance considered in term rewriting systems such as ones that reach fixed points.
    • A wise first step would be to examine the causal graph of our rule and try to collect as many "obvious" observations as possible.
    At first, it seems as though the causal graph might not look similar to the states graph, but running it for a few more iterations disproves that theory. This makes perfect sense as the reason why there wasn't "aggressive" looping in the causal graph for the first 7 iterations is due to the fact that there is only one shared state transition that connects the causal branches 1→3 and 1→ 4 when we only evolve the system 7 times. In fact, just running 3 more iterations of the causal graph gives an extremely similar structure to the multiway states graph, with similar loops "spawning" randomly:
    Instead, we attempt to establish the complexity of this multiway system by comparing it to other ones. So the rest of this section will be dedicated to relating this numerical multiway system to some common string replacement systems, as well as providing some intuition as to why the mergers are so hard to predict.
    Now taking a look at a more complex string substitution rule, {ABA → BBAA, BAA → AAB}
    Above is the multiway states graph for the string substitution system, and below is the causal states graph for the string substitution system.
    Notice how the complexity of the graphs seem to increase as our rules become more volatile (i.e. generating and destroying more "tokens" of A's and B’s) when we consider nontrivial starting cases. Indeed, as we increase the "volatility" of our string replacement rules, it seems as though the overall structure of the graph becomes more complex and the mergers become more challenging to predict. (Although predicting them still remain relatively easy).
    So how does this connect to numerical replacement functions? Well, in order to characterize the "volatility" of numerical replacement functions, we first need to utilize a property of integers that is easily defined/measurable. The most apparent property of integers that is measurable in this way is its prime factorization (and I can't really think of any other obvious ones). So if we utilize the prime factorization of the integers as a sort of token to track the volatility of the numerical replacement rules, the question of whether or not the relationship between the complexity of the graphs and the volatility of the replacement functions translates emerges.
    Note that the volatility of our replacement rules turn out to be completely generative: each operation generates one additional prime factor for the next state. So the volatility of our numerical replacement function can be defined as generating one additional prime factor "token" every operation. This results in a very simple structure in both the states and causal graph, so this system provides evidence that there seems to exist a correlation between how destructive/generative the replacement rules are and the complexity of the structure of the graphs of a multiway system.
    Although the first two cases seem to support our claim, it is necessary to either provide much more empirical data or to explicitly prove the connection between the volatility of our rules and the complexity of the graphs generated by those rules in order to make our claim more solid.
    However, two weeks is not enough time to individually analyze data for multiple types of numerical multiway systems, and consequently, we move on.

    Exactly how irregular are the paths?

    If the basis of the previous argument—that there exists a correlation between the volatility of the rules and the complexity of a graph generated from the rules—holds, then the next logical question would be "given the complexity of the graphs, how random will the paths to the mergers be?"
    To start off, it makes sense to first visualize the paths, one possible scheme to visualize the paths is to represent each 2x+1 operation as one movement in the positive x direction and to represent each 3x+1 operation as one movement in the positive y direction, and then to graph the paths to a merger accordingly:
    Code at the end of the article.
    When purely looking at the graphs, it is hard to spot any regularity between them. This leads to the question: how random are the paths to the mergers? As a sort of measure for how random the paths to the mergers are, we can find the entropy of the string. Note that this is by no means a perfect randomness test as it doesn't take into account the order of the functions, but it seems like the quickest solution given the amount of time I have left.
    Below is the code for generating the strings.
    We can then create a bar chart for each string:
    The entropy values seem to be roughly the same, with somewhat regular dips. So although the a's and b's seem to be randomly generated, there do seem to be patterns. Unfortunately, the entropy function is unable to account for the order in which the a's and b's occur, so if given more time, I would incorporate the order of the a's and b's with different test of randomness.

    Code

    First few mergers:

    Path to merger visualization:

    Conclusion

    Appendix: Connections to Push Down Automata (PDA)

    Now, just for fun: It is interesting that it is possible to establish a connection between PDA and our multiway graph such that when inputted a regular expression of "a"s and "b"s, we determine the movements of an “embedded token.” And although creating an PDA would not help with identifying mergers as the data will need to be sort of "preloaded" into the PDA, it’s pretty interesting that these two seemingly unconnected things can have a relationship. See below the state transition diagrams for creating such a PDA.
    The above PDA transition state diagram accepts a regular expression (regex) of operations *2, *3, +1 and keeps track of the movements in it's stack. And, as I mentioned above, it doesn't simplify our multiway system, but it is an interesting sort of "translation" connecting a numerical multiway system to an established part of theoretical computer science. I did not have the time to finish writing code for the PDA, but Tomas De Camino Beck's "Pushdown automata and context free grammars" is an extremely helpful resource.

    Code for visualizing a state transition graph: (adapted from Tomas De Camino Beck's "Pushdown automata and context free grammars") *For the appendix*

    References:

    ◼
  • Stephen Wolfram (2021), “The Concept of the Ruliad,” Stephen Wolfram Writings. writings.stephenwolfram.com/2021/11/the-concept-of-the-ruliad.
    • ◼
  • Wolfram, Stephen. Multicomputation with Numbers: The Case of Simple Multiway Systems—Wolfram Physics Bulletins. 7 Oct. 2021, https://www.wolframphysics.org/bulletins/2021/10/multicomputation-with-numbers-the-case-of-simple-multiway-systems/.
    • ◼
  • The Wolfram Physics Project: Finding the Fundamental Theory of Physics. https://www.wolframphysics.org/. Accessed 13 July 2023
    • ◼
  • De Camino Beck, Tomas. “Pushdown Automata and Context Free Grammars.” Community.Wolfram.Com, Wolfram Community, 13 July 2021, community.wolfram.com/groups/-/m/t/2377927. Accessed 09 July 2023.
    • ◼
  • De Camino Beck, Tomas. “Examples for Working with Finite State Automata - Online Technical Discussion Groups—Wolfram Community.” Wolfram Community, https://community.wolfram.com/groups/-/m/t/2355569. Accessed 13 July 2023.

    • Thanks:

    First, I would like to express my gratitude to Stephen Wolfram for developing the concept of the Ruliad and laying the groundwork for me. I would also like to thank the entire Wolfram Summer Research Program team as well as Stephen for the amazing opportunity to work on this project. I would also like to thank AnneMarie Torresen, my mentor, for her continual support and suggestions throughout my project. I would also like to express my gratitude to Jonathan Gorard for his invaluable direction, insights, and patience. Also, many thanks to Aaron Carver for reading through this and providing helpful thoughts and suggestions. To Henry Gustafon and Navvye Anand: thank you for the technical advice and discussions. And to the world: I hope you will find this a useful to learn more about the nature of the universe.

    CITE THIS NOTEBOOK

    On the mergers of numerical multiway systems​
    by Eric Archerman​
    Wolfram Community, STAFF PICKS, July 13, 2023
    ​https://community.wolfram.com/groups/-/m/t/2965206