Essays, Posts & Presentations

Confluence in Multiway Cellular Automata

Benjamin Jacobsohn

Author

Benjamin Jacobsohn

Title

Confluence in Multiway Cellular Automata

Description

Investigating the behavior and confluence of multiway cellular automata

Confluence in Multiway Cellular Automata

Benjamin Jacobsohn

This project is an investigation into confluence in multiway cellular automata. These systems were studied using the MultiwaySystem repository function. I measure confluence based on properties of the states graph for each system. I also investigate the general behavior of multiway cellular automata under different conditions. I found that most multiway elementary cellular automata are confluent, and that confluence changes depending on both the rule applied and the number of cells used. I found little correlation between the class of singleway elementary cellular automata and their multiway behavior, but some correspondence between their general behaviors. Future works includes investigating the CausalInvariantQ property of the MultiwaySystem function, and investigating universality in multiway systems.

Confluence in Multiway Cellular Automata

Singleway and Multiway Cellular Automata

In the simplest case of a normal, singleway Cellular Automaton (CA), rows of black and white cells are built up by applying a rule to each cell and its neighbors to find the color of each cell in the next row. This case corresponds to a one-dimensional, two-color, nearest-neighbor CA called an elementary CA. A multiway CA is a modification of this system where only one replacement from the rule is applied at one position per step. This is the behavior of elementary rule 110 as a singleway and multiway system:

Out[]=

Left: Singleway behavior of rule 110 from a random initial conditionRight: Multiway state transitions of rule 110 from all initial conditions of five cellsBottom: Plot of cell replacements corresponding to rule 110

Multiway CA’s can also be visualized by constructing singleway CA plots from different possible paths through the multiway system. This shows some of the possible paths through the states graph above starting from the single black cell initial condition:

Out[]=

This can also be viewed by overlaying these graphs to see the chance of cells being different colors at different steps, or by stacking the paths from different branches:

Out[]=

Testing for Confluence

This project aims to study confluence in multiway cellular automata. A graph is confluent where for every node, every branch from the node can always merge back into some other state. I also define total confluence as a graph where every node can always reach every other node, regardless of branching. For any multiway state graph, confluence can be shown by checking that for every disjointed piece of the graph, there is some state that every other state eventually connects to. This is tested for each island in the graph because only branches from the same state must merge. Total confluence can be tested by checking that every node is connected to every other node in its island from both directions at some distance. These methods should be applicable for any type of single-edge multiway system.

confluentQ[graph_] := AllTrue[WeaklyConnectedGraphComponents[graph], Function[cc, AnyTrue[VertexList[cc], ContainsExactly[VertexInComponent[cc, #], VertexList[cc]] &]]]totalConfluentQ[graph_] := CompleteGraphQ[TransitiveClosureGraph[graph]]

This is the states graph for rule 110 from every initial condition. This graph is confluent, as all the outside states from the main subgraph can always reach one of the states in the central loop. It is not totally confluent, as the outside states cannot be reached from the inside ones, and the all white state cannot reach or be reached by any other state:

Out[]=

Confluent: True

Total Confluent: False

I call the states which the system can always reach confluent end states. In this case, the confluent end states are the central connected portion of the graph, as well as the all white island state:

In[]:=

getConfluentEndStates[graph_]:=Function[cc,Select[VertexList[cc], ContainsExactly[VertexInComponent[cc,#],VertexList[cc]]&]]/@WeaklyConnectedGraphComponents[graph]

Out[]=

Confluence by Rule Behavior

Cellular automata can be divided into four classes based on their behavior. Class 1 automata quickly become uniform, class 2 repetitive, class 3 appear mostly random, and class 4 have localized structures interacting in complex ways. This chart shows the singleway behavior of three automata from each class, along with the states graph and confluence of their corresponding multiway systems:

Out[]=

It’s impossible to draw concrete conclusions from this small sample size, especially because there is only one distinct class 4 elementary CA, but I will generalize some observations nonetheless. Qualitatively, there does not seem to be a correlation between rule class and confluence, but the structure of the state graphs are generally similar for rules with similar singleway behavior. Class 1 automata must maintain their states after a certain point by definition. Class 2 automata seem to produce multiway state graphs with a more regular structure, though the complex repeated pattern of singleway rule 154 does not lend itself to a straightforward states graph representation. Class 3 automata show very complicated branching paths that aren’t easy to analyze, much like their singleway counterparts. All of the class 4 elementary automata are simple transformations of rule 110, but seem to produce state graphs with slightly different structures. They all have a mostly regular form with some complications, which could be related to their singleway behavior of a regular background with pockets of complex interactions.

More Multiway CA Behaviors

I mostly studied small cell tape widths, as any representation of any multiway CA grew in size and complexity much faster than for singleway systems. I found that the behavior of many rules changed for different numbers of cells, including whether or not the system was confluent. This shows the states graph structure for one rule from each class from all initial conditions of different cell tape widths:

Out[]=

I found that most multiway elementary CA rules are confluent, but that confluence depends on the width of the cell rows as well as the rule . Only a few multiway CA' s were totally confluent . Confluence of one rule can fluctuate based on cell tape width in a variety of ways.

Out[]=

	Confluent
	Total Confluent

So far I’ve only shown the states graph for multiway cellular automata. A complimentary view is the causal graph, which shows the interactions between different rule applications directly. This shows the structure of the states graphs and causal graphs for multiway rule 110 for cell tape widths up to five, along with their confluence and the CausalInvariantQ property from the MultiwaySystem function:

Out[]=

Max Piskunov observed that the CausalInvariantQ property actually measured confluence, but that isn’t consistent with these examples. It does not seem to measure causal invariance here either, as the It’s possible that the CausalInvariantQ property does not correctly identify either confluence or causal invariance for non-terminating systems, which may be a problem with the function or with the definition of these terms for non-terminating systems such as these. In general, these multiway cellular automata start to show some forms of complex behavior with around four cells. I’ve also found some complexity with using single-neighbor rules (instead of looking at neighbors on both sides). This shows the states graph and causal graph structure for the first eight of these single-neighbor rules with five cells after three steps:

Out[]=

Concluding Remarks

I found that most multiway elementary CA rules are confluent, but that confluence depends on the width of the cell rows as well as the rule. Only a few multiway cellular automata were totally confluent. Confluence of one rule can fluctuate based on row width in a variety of ways. The behavior of multiway cellular automata seem to be somewhat related to that of their singleway counterparts, but with a very limited sample size I did not find a correlation between the behavior class of a singleway CA and the confluence of its corresponding multiway CA. Confluence can be an important property to define how a multiway system can be viewed as a computation, with confluent end states being possible results of the computation. It may also be related to the universality of a multiway system. The description and measure of confluence from this project can also be applied to all types of multiway systems, not just cellular automata. I would like to study the relationship between confluence of a multiway CA and the behavior of its singleway counterpart in more detail. This would probably require an automatic classification system of the behavior of singleway cellular automata. It’s also difficult to find concrete results as there is only one truly distinct elementary CA with class 4 behavior. So, I would also like to study different classes of CA rules. The next step is to study the relationship between causal variance and confluence. Causal variance is a property similar to confluence but for the causal graph of the system, which shows how different updating events affect each other. I did not find an immediate correlation between these properties, but the CausalInvariantQ property of the MultiwaySystem resource function does not seem to work properly in all cases. So, I need to figure out the issues and fix them before continuing in this direction. An important idea that is not yet well understood is universality in multiway systems. Simple systems including singleway elementary cellular automata have been shown to be universal, meaning they can emulate any other system. However, it is not clear that universality can be defined in the same way for multiway systems, or if singleway systems can emulate all multiway systems. It seems possible that universality in multiway systems can be defined in terms of correspondence between causal graphs, but this requires more investigation.

Keywords

◼

Multiway Systems

◼

Cellular Automata

◼

NKS

◼

Confluence

◼

Causal Invariance

Acknowledgements

I would like to thank Christopher Wolfram for being an excellent mentor and guiding me through many aspects of this project from understanding to code and for helping make the summer school a very enjoyable experience. I’d also like to thank Stephen Wolfram for providing the project idea and for pushing me to understand more about the ways multiway systems can behave. Thanks to Jonathan Gorard for his work on creating the extremely extensive MultiwaySystem repository function which provided the foundation for my project, and for helping me understand how to use it properly. Additionally, thanks to Max Piskunov for his work on understanding the relationship between confluence and causal invariance, contributing to the MultiwaySystem function, and understanding how the function measures causal invariance. Finally, thanks to all the administrators at the Wolfram Summer School, including Erin Cherry, Danielle Mayer, and Mads Bahrami, for making this experience possible.

References

◼

Confluence and Causal Invariance - Max Piskunov

◼

https://www.wolframphysics.org/bulletins/2020/11/confluence-and-causal-invariance/

◼

Mulitway Turing Machines - Stephen Wolfram

◼

https://www.wolframphysics.org/bulletins/2021/02/multiway-turing-machines/

◼

MultiwaySystem repository function - Jonathan Gorard, Max Piskunov, Stephen Wolfram

◼

https://resources.wolframcloud.com/FunctionRepository/resources/MultiwaySystem

Cite this as: Benjamin Jacobsohn, "Confluence in Multiway Cellular Automata" from the Notebook Archive (2021), https://notebookarchive.org/2021-07-6hr5pdq