A Class of Models with the Potential to Represent Fundamental Physics
  1. Introduction
  2. Basic Form of Models
  3. Typical Behaviors
  4. Limiting Behavior and Emergent Geometry
  5. The Updating Process for String Substitution Systems
  6. The Updating Process in Our Models
  7. Equivalence and Computation in Our Models
  8. Potential Relation to Physics
  9. Additional Material
  10. References
  11. Index

5.3 States Graphs

If there are multiple successors to a particular state in a substitution system one thing to do would be just to assume that each of these successors is a new, unique state. The result of this will always be to produce a tree of states, here shown for the rule {A BBB, BB A}:

LayeredGraphPlot[ ResourceFunction["MultiwaySystem"][{"A" -> "BBB", "BB" -> "A"}, "A", 5, "EvolutionGraphUnmerged"], AspectRatio -> .4]

But in our construction of multiway systems, we assume that actually the states produced are not all unique, and instead that states at a given step consisting of the same string can be merged, thereby reducing the tree above to the directed graph:

Graph[ResourceFunction["MultiwaySystem"][{"A" -> "BBB", "BB" -> "A"}, "A", 5, "StatesGraph"], AspectRatio -> 1.5]

But if we are going to merge identical states, why do so only at a given step? Why not merge identical states whenever they occur in the evolution of the system? After all, given the setup, a particular statewherever it occurswill always evolve in the same way, so in some sense it is redundant to show it multiple times.

The particular rule {A BBB, BB A} that we have just used as an example has the special feature that it always “makes progress” and never repeats itselfwith the result that a given string only ever appears once in its evolution. Most rules, however, do not have this property.

Consider for example the rule {AB BAB, BA A}. Starting from ABA, here is our normal “evolution graph”:

LayeredGraphPlot@ ResourceFunction["MultiwaySystem"][{"AB" -> "BAB", "BA" -> "A"}, "ABA", 4, "EvolutionGraph"]

Notice that in this evolution even the original state ABA appears again, both at step 3 and at step 5and each time it appears, it necessarily makes a complete repeat of the same evolution graph. To remove this redundancy, we can make a graph in which we effectively merge all instances of a given state, so that we show each state only once, connecting it to whatever states it evolves to under the rule:

GraphPlot[ ResourceFunction["MultiwaySystem"][{"AB" -> "BAB", "BA" -> "A"}, "ABA", 4, "StatesGraph", "IncludeEventInstances" -> True], GraphLayout -> {"LayeredDigraphEmbedding", "RootVertex" -> "ABA"}]

But in this graph there are, for example, two connections from ABA to BABA, because this transformation happens twice in the 4 steps of evolution that we are considering. But in a sense this multiplicity again always gives redundant information, so in what we will call our “states graph” [1:p209], we only ever keep one connection between any given pair of states, so that in this case we get:

GraphPlot[ ResourceFunction["MultiwaySystem"][{"AB" -> "BAB", "BA" -> "A"}, "ABA", 4, "StatesGraph"], GraphLayout -> {"LayeredDigraphEmbedding", "RootVertex" -> "ABA"}]

There is one further subtlety in the construction of a states graph. The graph only records which state can be transformed into which other: it does not record how many different replacements could be applied to achieve this. In the rule we just showed, it is never possible to have different replacements on a single string yield the same result.

Consider the rule {A AA, A B} starting with AA. There are, for example, two different ways that this rule can be applied to AA to get AAA:

LayeredGraphPlot@ ResourceFunction["MultiwaySystem"][{"A" -> "AA", "A" -> "B"}, "AA", 2, "EvolutionGraphFull"]

In our standard states graph, however, we show only that AA is transformed to AAA, and we do not record how many different possible replacements can achieve this:

LayeredGraphPlot@ ResourceFunction["MultiwaySystem"][{"A" -> "AA", "A" -> "B"}, "AA", 2, "EvolutionGraph"]

The degree of compression achieved in going from evolution graphs to states graphs can be quite dramatic. For example, for the rule {BA AB, AB BA} the evolution graph is

LayeredGraphPlot@ ResourceFunction["MultiwaySystem"][{"BA" -> "AB", "AB" -> "BA"}, "BABA", 6, "EvolutionGraph"]

and the states graph is

GraphPlot[ ResourceFunction["MultiwaySystem"][{"BA" -> "AB", "AB" -> "BA"}, {"BABA"}, 6, "StatesGraph"], GraphLayout -> {"LayeredDigraphEmbedding", "RootVertex" -> "BABA"}]

or in our standard rendering:

ResourceFunction["MultiwaySystem"][{"BA" -> "AB", "AB" -> "BA"}, {"BABA"}, 6, "StatesGraph"]

Note that causal invariance works the same in states graphs as it does in evolution graphs: if a rule is causal invariant, any two paths that diverge must eventually reconverge.