Looking for multiway systems of intermediate growth​
​by Yorick Zeschke

Introduction

Especially since the recent developments in the Wolfram Physics Project, the study of multiway systems has become a very interesting and far-reaching topic. In this project, I investigate the growth of multiway systems, meaning the number of new (previously nonexistent) states added to the system in every iteration. After building an intuition for the different types of multiway systems there are, I come up with a basic classification scheme to characterize multiway systems by their growth. Besides empirically investigating some systems, I use the classification scheme to build “maps of multiway system space” and search through a large amount of multiway systems. I find a couple of interesting systems as well as some candidates for "intermediately growing" systems which will be explained later.

Growth of Multiway Systems

Like a regular substitution system, a multiway system repetitively applies replacement rules to some initial state (in our case a string). But instead of following a prescribed application order of the rules, the multiway system takes all possible paths, applying the rules in every possible way. In the states graph, we see how one state can be used in different ways to generate other states by applying the replacement rules.
In[]:=
ResourceFunction["MultiwaySystem"][{"AB""A","AA""AAA"},"AAABBA",3,"StatesGraph"]
Out[]=
As we can see, some replacements lead to the same states. Additionally, replacements in the nth iteration can produce states from previous iterations, leading to cycles in the states graph.
In[]:=
ResourceFunction["MultiwaySystem"][{"AA""A","AB""ABA"},"ABABBA",2,"StatesGraph"]
Out[]=
For the growth of a multiway system, we only consider new (previously nonexistent) states added to the system in every iteration. In other words: we only look at the merged states of the system. The sequence generated this way is called the “growth sequence” of a multiway system. By only considering merged states, every multiway system with finitely many states in total (called a “finite multiway system”) has zero new states at some point. Finite multiway systems have some interesting properties but are not as relevant for the Physics Project and will not be investigated here.

[Details] Efficient Implementation of Multiway Systems

To be able to analyze a large amount of multiway systems, we use an efficient implementation provided by Stephen Wolfram and Jonathan Gorard.
In[]:=
MultiwayGrowthListHashSet[rule_,init_List,t_]:=​​Last/@​​NestList[​​Function[s,​​ {Join[First[s],#],#}&[Module[{list,hashSet},​​ Normal[CreateDataStructure["HashSet"]["Union",Flatten[StringReplaceList[Last[s],rule]]]["Complement",First[s]]]]]],{{},init},t]
In[]:=
growth[rule_,init_List,steps_]:=Length/@MultiwayGrowthListHashSet[rule,init,steps]

Some Basic Investigations


Common Types of Multiway System Growth

From the plots above, we can think of some basic classes that multiway systems could belong to. It seems like, after some turbulence at the beginning, multiway systems either
◼
  • have a finite number of states, meaning they stop growing at some point
    • In[]:=
    ListLinePlot[growth[rules[[13]],{"ABAB"},10]]
    Out[]=
    2
    4
    6
    8
    10
    0.5
    1.0
    1.5
    2.0
    ◼
  • grow linearly
    • In[]:=
    ListLinePlot[growth[rules[[8]],{"ABAB"},10]]
    Out[]=
    2
    4
    6
    8
    10
    2
    4
    6
    8
    10
    ◼
  • or grow exponentially
    • In[]:=
    ListLinePlot[growth[{"AB""ABAB","BA""ABA"},{"ABABAB"},10],AspectRatio1]​​ListLinePlot[Log/@growth[{"AB""ABAB","BA""ABA"},{"ABABAB"},10],AspectRatio1]
    Out[]=
    2
    4
    6
    8
    10
    500
    1000
    1500
    2000
    Out[]=
    2
    4
    6
    8
    10
    2
    4
    6
    8
    There are also multiway systems which seem to grow polynomially but not linearly, but they are rarer and usually more complex. After looking at more examples, I suspect that most multiway systems grow either polynomially or exponentially. This makes sense intuitively: something as discrete as a multiway system is not very likely to grow like
    Sin[Log[x]]
    
    or some other "complicated" function. Of course, this intuition proves nothing but there is empirical evidence that most multiway systems grow approximately like a polynomial or like Exp of some polynomial. However, there might be multiway systems exhibiting “intermediate growth”.

    Intermediate Growth and its Importance

    A function f is said to grow intermediately if
    ln(f(x))
    ln(x)
    →∞
    for
    x→∞
    while
    ln(f(x))
    x
    →0
    for x → ∞. This expresses the idea that f grows faster than every polynomial and slower than every exponential function. Intermediate growth can analogously be defined for sequences. We say, a multiway system "grows intermediately" if its growth sequence grows intermediately.
    The related problem of finding groups of intermediate growth has been unsolved for thirty years before Grigorchuk manually constructed a group of intermediate growth. Even though there are similarities between multiway systems and algebraic structures, I was not able to construct a multiway system of intermediate growth from a group or semigroup. This seems like a promising approach for further research though.
    But why should the search for multiway systems of intermediate growth be interesting? To see this, just think of a function which grows intermediately. It is not trivial to come up with one if you never heard of the concept before. One example of such a function is
    x
    
    as you can easily verify be the definition above. But now try to think of a multiway system for which the number of new states in every iteration is described by this or a similar function. Apart from the fact, that
    x
    
    and similar functions do not yield natural numbers for most x, a system growing like this function must be very complex and show intricate patters and structures.
    This complexity is exactly the reason for why we are interested in finding such systems. Especially in the context of volume entropy, multiway systems of intermediate growth might be relevant for the Wolfram Physics Project. Also when considering their (conjectured) intricacy, they could be more likely to appear in candidate universes. Last but not least, the question of the existence of such systems could be very useful for making statements about multiway causal graphs which are used in the Physics Project.
    Having all that said, it is time for us to finally explore the growth of multiway systems in more depth.

    Investigating a Single Candidate System

    By generating some more plots and iteratively improving my filters for “interesting” multiway systems, I found quite some very complex systems after the first couple of days of project time. The process of simulating a multiway system which grows faster than linearly can quickly become very computationally intensive. Therefore, I used the experimental AWS Integration for Wolfram Language from Jesse Friedman and this notebook contains only the precomputed results.
    Let us have a look at one of my favourites.
    Rule number nine was one of the first candidates for systems of intermediate growth. But it is not only the specific rule that is responsible for the growth of a multiway system. The initial condition is probably equally important. A very complex system can become very boring if it is fed with the wrong initial condition. Have a look at rule number 9 with initial condition “ABAB”. If you recall the image from above, you notice plain linear growth.
    Now however, consider the same rule with the initial condition "ABABBA":

    Another system we have to look at

    One of my next steps will definitely be to have a closer look at the structure of this system. For now, let us not focus so much on single candidates but on the overall system space.

    The Classification Scheme

    Formalising the types of multiway systems listed in the introduction, I came up with seven classes to describe the degree of "interestingness" a certain multiway system has from the perspective of this project. Almost all the classification is done by trying to fit a function through the growth sequence generated by the system and then analysing that function. The class a multiway system will fall in is determined by the class of the "easiest" function that fits its growth sequence reasonably well and that functions asymptotic behavior (if known). Of course, we can’t be sure, that this approach classifies the multiway system correctly, but usually it doesn’t overestimate the system’s complexity, helping us to narrow down our search.

    Examples

    Speaking of complexity, I want to point out some cases for which this classification scheme is simply not ready yet. As a first example, we can consider the notorious "periodic after 1071 steps"-system from A New Kind of Science. Note well, that the plots at the bottom of the page in NKS describe the growth for the unmerged states case (which is not relevant for us, as explained here).
    The growth looks very complex or even chaotic, but when considered over a few more steps, the system seems to approximately grow linearly.
    Still, the system is too complex to be classified by my function correctly.
    After having seen what our function cannot classify, it is satisfying to watch how well it actually does for some easier systems.
    There are quite some things going on here: we see that the classification function is not disturbed by the turbulence at the beginning of rule 9 which was expected. Next, we notice the strange function it found for system 3 so we probably want to have a closer look on especially this one in the near future. Additionally, the classifier confirms our conjecture about the fourth system (rule 31) being complex.
    I could talk a lot more about in which cases this classifier is useful and how it should be extended but right now, the only thing I can do in the remaining time is applying it - which turns out to be a very good decision. Before we jump right in, I just want to point out that the classifier is non-deterministic, because it partially relies on FindFormula which I have not yet got to work without random starting conditions.

    Maps of Multiway System Space

    Using the classification scheme, we can assign a characteristic number to every multiway system belonging to a certain part of “Multiway System Space”. Out of this space, we cut a piece with two dimensions: the rule dimension and the initial condition dimension. While there are only finitely many rules of a certain signature, there can be infinitely many initial conditions. I suspect however, that multiway systems arising from long initial conditions can be broken down and described or at least approximated by systems starting form shorter initial conditions.
    Before going into more details, let us just draw such a map. Despite only simulating every system for 20 steps and setting time limits in the classification function, this mapping takes some computational effort because some systems run long for many initial conditions or some initial conditions seem to produce more long-running systems. I would not suggest running the following cell without a cloud architecture.
    As indicated by the legend, the colours of the map correspond to the growth classes defined above. We immediately see that white is the dominant colour, meaning most multiway systems terminate. It is also possible to quantify this observation:
    Interestingly enough, there are a lot of systems described by holonomic or recursive sequences as well, but not a single one that looks like a simple exponential function. This can be due to the fact that the rules of signature {2->1, 2->3} generally restrict the growth rate to sub-exponential. Another very surprising fact is the existence of 76 systems classified as intermediate growth. One definitely has to look more into this but I presume this happened because we only ran the systems for 20 steps. Better maps with more steps are currently being made.
    When looking at the map for a while, there definitely seem to be patterns. It surely does not look random, but at least I personally had the feeling the map had been cut in vertical stripes which were arranged in the wrong order so that the overall picture is not very consistent. Indeed, this is probably the case because until now I have not found an optimal arrangement where rules with small edit distance are as close to each other as possible. I assume that such an arrangement would make patterns more obvious because rules with small edit distance will cause roughly similar behavior in multiway systems.
    This is supported by the argument that I already did arrange the initial conditions in a meaningful way, specifically a gray code, meaning that between two consecutive rules only one single letter changes.
    I reversed some of the gray codes in the above call to assure that the gray code condition is preserved if the length of strings increase.
    Even without a perfect arrangement of the rules, there are these very curious structures which I will definitely have a closer look at. Talking of curious structures, I want to mention one thing that I noticed only very recently. Have a look at the plots of some multiway systems "close to each other" (in terms of very similar initial conditions).
    It is easy to recognize the similar shapes of the plots. This motivates the conjecture, that systems with long initial conditions could be predicted by analysing shorter initial conditions and "breaking down" the systems.

    Conclusion

    While I was not able to formally prove, for any given multiway system, it grows intermediately, I found some very interesting candidate systems which have to be investigated further. In addition to that, I started developing a framework for analysing the growth of multiway systems and classifying them based on the analysis. This framework is not nearly complete yet but it can be a good start to help exploring multiway system space and finding more interesting candidates. All in all, this project can only give hints to what has to be done and I am looking forward to continuing my research in this domain.
    Some explicit suggestions for further investigation include:
    ◼
  • Extending the amount of multiway system space mapped (important, but computationally expensive)
    • ◼
  • Improving the arrangement of rules in the multiway system space maps and continue searching for patterns
    • ◼
  • Making the classes more subtle and flexible (no hard-coded parameters) and add classes based for handling systems where no explicit growth function can be found
    • ◼
  • Trying to use automated theorem provers to find the growth function of a given multiway system
    • ◼
  • Finding ways to programmatically deduce to asymptotic growth from a holonomic sequence (RSolve and friends rarely work on the ones I have)
    • ◼
  • Defining a distance metric for multiway systems to better explore multiway system space (for example it might be possible to come up with some gradient-decent like search)

    • Keywords

    ◼
  • Multiway Systems
    • ◼
  • Growth of Multiway Systems
    • ◼
  • Intermediate Growth
    • ◼
  • Classification of Multiway System