Abstract: Network mobile automata (NMA) are systems in which clusters of nodes in a hypergraph are transformed based on rules that not only change the shape of the cluster but also assigns a tag to one particular edge and moves it around as the system evolves. The labeled hyperedge is analogous to a mobile head, like in a Turing machine, and by testing various initial conditions and rules characterized by hypergraph rule signatures, we strive to understand the evolution behavior of the NMA. This project revealed early signs of complex behavior and by optimizing the process for checking hypergraph isomorphisms, we may be able to find even more unpredictable evolution. Also, there is more investigation to be done to characterize planarity-preserving rules, which preserve dangling edges, and the types of evolutions they would lead to.
Introduction
Introduction
Mobile Automata and Network Evolution
Mobile Automata and Network Evolution
In basic cellular automata, you start with an initial condition consisting of cells colored in a specific pattern and evolve the system accordingly. Normally, the evolution is represented by the next step drawn right below the previous state in parallel. However, mobile automata add a new condition to this system. An active cell is added to indicate where the rule would be applied specifically and the evolution rules decide where the head would be next. As the system progresses, you can observe how the active cell moves through the system as well as the color pattern of the cellular automata. Figure 1 is an example of a mobile automaton rule (the black dot indicates the active cell) and Figure 2 demonstrates a system evolving under this rule.
In[]:=
Labeled[CloudGet["https://wolfr.am/nks-page0071b-graphic"],"Figure 1"]
Out[]=
Figure 1 |
In[]:=
Labeled[CloudGet["https://wolfr.am/nks-page0071a-graphic"],"Figure 2"]
Out[]=
Figure 2 |
A network, on the other hand, evolves using replacement rules applied whenever there’s a match to a specific pattern in the network graph. The examples in Figure 3 demonstrate a nested property where the one can see the pattern going into deeper layers and a limiting geometry is revealed. Network evolutions can show nested, repetitive, or random behavior.
In[]:=
Labeled[CloudGet["https://wolfr.am/nks-page0509a-graphic"],"Figure 3"]
Out[]=
Figure 3 |
Network Mobile Automata
Network Mobile Automata
In Chapter 9, Section 12 of Stephen Wolfram’s A New Kind of Science, Wolfram includes a brief note about the Network Mobile Automata (NMA), a network of nodes that evolves based on rules constrained by the location of a mobile head. The head locates where the transformation will happen, and the rule changes the structure of the graph and the position of the head.
In[]:=
Labeled[CloudGet["https://wolfr.am/nks-page1040a-graphic"],"Figure 4"]
Out[]=
Figure 4 |
In this project, I started with creating a framework in which to study the NMA by turning such systems and rules into analogous hypergraph and hypergraph rewriting rules. I aimed to study the ruliology of these network systems and the multiway evolution that can occur even though NMA updates can only take place around the head. The reader may notice that in the original NMA, the head is placed on a vertex. Consider, however, that the purpose of the head is to mark the location of the transformation as well as where it’ll go next. An edge can encode both the starting and ending location of a vertex in the network system so this is a valid way of modeling the NMA.
This post will cover the code that I wrote and used to generate the ruliology of the NMA, early observances of the evolution, and future paths of study for this topic.
This post will cover the code that I wrote and used to generate the ruliology of the NMA, early observances of the evolution, and future paths of study for this topic.
Computation
Computation
Hypergraph
Hypergraph
This project mainly used the Hypergraph Paclet from the Wolfram Paclet Repository written by Nik Murzin and Carlos Zapata Carratalá to generate the initial conditions and hypergraph rules as well as get information from these hypergraphs.
In[]:=
PacletInstall["https://www.wolfr.am/Hypergraph.paclet",ForceVersionInstall->True]<<WolframInstitute`Hypergraph`
Out[]=
PacletObject
A network is represented by a hypergraph where the nodes are vertices of the hypergraph and the nodal connections are hyperedges. Below are some examples of initial conditions tested during this project.
In[]:=
init=Hypergraph[{{1,2}->h,{1,3},{1,4},{2,3},{3,4},{4,2}},EdgeLabels->"EdgeTag",GraphLayout->"TutteEmbedding",ImageSize->Tiny]
Out[]=
In[]:=
init2=Hypergraph[{{1,2}->h,{2,3},{1,4},{3,4},{5,6},{6,7},{7,8},{8,5},{5,1},{2,6},{3,7},{4,8}},EdgeLabels->"EdgeTag",GraphLayout->"TutteEmbedding",ImageSize->Tiny]
Out[]=
The initial states chosen in this project were inspired from NKS and were mostly used for their simplicity. Few incomplete graphs were tested but most of the analysis in this project can be applied using the simple initial conditions above.
The NMA rules can be represented as hypergraph rewriting rules. Below shows how the top rule in Figure 4 would be written as a hypergraph rewriting rule.
rule=HypergraphRule[Hypergraph[{{1,2}->h,{1,3},{1,4}},EdgeLabels->"EdgeTag"],Hypergraph[{{1,5}->h,{1,6},{5,6},{1,2},{5,3},{6,4}},EdgeLabels->"EdgeTag"]]
Out[]=
It’s important to note that vertex names are preserved between the left and right hand sides of each rule so some rules that may seem isomorphic are actually describing different transformations. For example, the first rule below keeps the same edge as the head and simple adds the {1,4} onto the pattern. In the second rule, however, the head edge is moved is moved to the {1,3} edge then {1,4} is added. So these two are not technically equivalent rules.
In[]:=
//FullForm
//FullForm
Out[]//FullForm=
HypergraphRule[Hypergraph[List[1,2,3],Hyperedges[Rule[List[1,2],h],List[1,3]],Rule[EdgeLabels,List[Rule[Blank[],"EdgeTag"]]]],Hypergraph[List[1,2,3,4],Hyperedges[Rule[List[1,2],h],List[1,3],List[1,4]],Rule[EdgeLabels,List[Rule[Blank[],"EdgeTag"]]]]]
Out[]//FullForm=
HypergraphRule[Hypergraph[List[1,2,3],Hyperedges[Rule[List[1,2],h],List[1,3]],Rule[EdgeLabels,List[Rule[Blank[],"EdgeTag"]]]],Hypergraph[List[1,2,3,4],Hyperedges[List[1,2],Rule[List[1,3],h],List[1,4]],Rule[EdgeLabels,List[Rule[Blank[],"EdgeTag"]]]]]
One difference between the original formulation of the NMA and our approach is that the edges are undirected in these hypergraphs. This means that at any given state, either of the two end points on the edge can be considered the starting location and the end location. Though this deviates from the initial proposition of the NMA, I believed this would allow for multiway evolution and more interesting long term behavior.
Isomorphisms and Canonicalization
Isomorphisms and Canonicalization
An important aspect of this process was to identify instances of hypergraph isomorphism to ensure that rules and vertices of multiway graphs were not duplicated in our systematic search. Although we saw multiway behavior in evolution due to the undirected head edges in our hypergraphs, there were often symmetries in the rule or the initial condition that led to output states always being isomorphic. The Hypergraph paclet came with an IsomorphicHypergraphQ function that compares two hypergraphs and verifies whether they are isomorphic or not. There were also CanonicalHypergraph and CanonicalHypergraphRule that took a hypergraph/hypergraph rule and gave its canonical form.
Hypergraph Rewriting Rules
Hypergraph Rewriting Rules
To test various rules of similar structure, I first generated hypergraph rewriting rules of specific signatures using the EnumerateWolframModelRules function from the Wolfram Function Repository. Then the undirectedHypergraphsToNMARules function that I produced would turn this list into to a list of NMA rules.
undirectedHypergraphsToNMARules[rules_List]:=Module[{hyperlhs,hyperrhs,indiceslhs,indicesrhs,newlhs,newrhs},hyperlhs=#["EdgeList"]&/@(DeleteDuplicates[Hypergraph[First[#]]&/@rules,IsomorphicHypergraphQ]);hyperrhs=#["EdgeList"]&/@(DeleteDuplicates[Hypergraph[Last[#]]&/@rules,IsomorphicHypergraphQ]);indiceslhs=DeleteDuplicates[#]&/@(Flatten[#]&/@Table[Position[hyperlhs[[#]],hyperlhs[[#]][[i]],1,1],{i,Length[hyperlhs[[#]]]}]&/@Range[Length[hyperlhs]]);indicesrhs=DeleteDuplicates[#]&/@(Flatten[#]&/@Table[Position[hyperrhs[[#]],hyperrhs[[#]][[i]],1,1],{i,Length[hyperrhs[[#]]]}]&/@Range[Length[hyperrhs]]);newlhs=DeleteDuplicates[Hypergraph[#,EdgeLabels->"EdgeTag"]&/@Flatten[Table[ReplaceAt[hyperlhs[[i]],edge_List:>(edge->h),#]&/@Flatten[indiceslhs[[i]]],{i,Length[hyperlhs]}],1],IsomorphicHypergraphQ];newrhs=Hypergraph[#,EdgeLabels->"EdgeTag"]&/@Flatten[Table[ReplaceAt[hyperrhs[[i]],edge_List:>(edge->h),#]&/@Flatten[indicesrhs[[i]]],{i,Length[hyperrhs]}],1];DeleteDuplicates[Parallelize[Apply[HypergraphRule,#]&/@Tuples[{newlhs,newrhs}]],(CanonicalHypergraphRule[#1]===CanonicalHypergraphRule[#2])&]]
It’s interesting to note here that it is not quite clear just from looking at these rules how the newly generated hyperedges and nodes will fit in the NMA state. For example, in the very last rule, the rule simply generates a brand new binary relation out of thin air. Where does this binary relation go? How does this affect the network’s shape overall? This brings up the “dangling connections” criterion first mentioned in NKS in regards to network evolution, which will be explored in depth later. In regards to this last rule, when applied to the first initial condition from earlier, we see the following evolution:
Generating Multiway Graphs
Generating Multiway Graphs
To actually output the ruliology, I first started off by writing the canonicalForm function which canonicalizes all the results due to an NMA rule being applied to a system then removes the duplicates. This was so that when I create the nested graph applying canonicalForm repeatedly, isomorphic states in the multiway graph are already removed.
Then the ruliology function written by me then takes an initial condition, a rule, and the number of computational steps and outputs a nested graph that tracks the evolution of the given NMA. If a rule does not apply to the initial condition, it will output a blank graph.
Observations
Observations
Simple Behavior
Simple Behavior
Multiway Behavior
Multiway Behavior
Preserving dangling edges
Preserving dangling edges
In both these rules, we see the rule preserving the “outer shape” of the network while adding smaller details within it as the system evolves. In NKS, it was discussed even combining two rules to see complex evolution that didn’t demonstrated nested patterns as we see above or repeated behavior. Although I was not able to implement this rule mixing specifically, it shows that if we are able to enumerate edge-preserving rules, we will be one step closer to finding more interesting behavior worth studying.
Final Statement and Further Areas of Study
Final Statement and Further Areas of Study
When we restrict the location of network evolution based on this mobile head edge, we can start to see multiway evolution. Though seemingly simple for now, there is much potential for the ruliology of Network Mobile Automata to match behaviors of multiway Turing machines and other complex systems. Understanding the patterns and limiting behavior of specific rules could lead to more parallels between fundamental physics and the computational structures at the heart of the Wolfram Physics Project. This project has only begun to scratch the surface of network mobile automata and there are two major threads future investigations can get started on.
First of all, the limited efficiency of available resources severely hindered the productivity and amount of data to study. As mentioned earlier, this project utilized the Hypergraph paclet to create the hypergraphs, compare the head edges, and canonicalize the hypergraphs. However, the ruliology function that implemented these functions to get rid of isomorphic vertices in the multiway graph took unreasonably long to compute and oftentimes crashed the kernel. If I can make this process more efficient, I could compare and study much more cases and observe the limiting behavior of NMA systems. It’s important to note that none of the functions were intended to be used with edge heads as a factor in determining isomorphism and this could be the reason to the processing time.
With the technical issues resolved, classifying rules that preserve “dangling connections” would be valuable to study a wider range of evolutions that produce nontrivial results. Rules that simply replaced edges with self-loops or destroyed nodes due to unconnected edges quickly led to trivial behavior such as “unraveling” (each vertex is in two edges at maximum) or “deconstruction” (the system heads towards vertices with 0-arity relations). The first steps of such enumeration would involve deciding how many of these connections one would like on each side and how they would describe the behavior within those ends. There is no real limit to how complex a rule can be within those dangling ends and it’s still possible to get trivial behavior from such rules. If one wishes to add symmetry, they can implement a restriction by saying all vertices except the ones at the dangling ends have the same degree. And finally, we could look for a way to combine two of these kind of rules together in some alternating fashion to replicate the complex behavior demonstrated in NKS. Stephen Wolfram says at the end of the section on network evolution that “if one manages to find the ultimate rules for the universe, [...] they will give rise to networks that on a small scale look largely random” (515). And as he predicts, I believe studying complex edge-preserving NMA rules will progress our understanding of such random evolving networks.
First of all, the limited efficiency of available resources severely hindered the productivity and amount of data to study. As mentioned earlier, this project utilized the Hypergraph paclet to create the hypergraphs, compare the head edges, and canonicalize the hypergraphs. However, the ruliology function that implemented these functions to get rid of isomorphic vertices in the multiway graph took unreasonably long to compute and oftentimes crashed the kernel. If I can make this process more efficient, I could compare and study much more cases and observe the limiting behavior of NMA systems. It’s important to note that none of the functions were intended to be used with edge heads as a factor in determining isomorphism and this could be the reason to the processing time.
With the technical issues resolved, classifying rules that preserve “dangling connections” would be valuable to study a wider range of evolutions that produce nontrivial results. Rules that simply replaced edges with self-loops or destroyed nodes due to unconnected edges quickly led to trivial behavior such as “unraveling” (each vertex is in two edges at maximum) or “deconstruction” (the system heads towards vertices with 0-arity relations). The first steps of such enumeration would involve deciding how many of these connections one would like on each side and how they would describe the behavior within those ends. There is no real limit to how complex a rule can be within those dangling ends and it’s still possible to get trivial behavior from such rules. If one wishes to add symmetry, they can implement a restriction by saying all vertices except the ones at the dangling ends have the same degree. And finally, we could look for a way to combine two of these kind of rules together in some alternating fashion to replicate the complex behavior demonstrated in NKS. Stephen Wolfram says at the end of the section on network evolution that “if one manages to find the ultimate rules for the universe, [...] they will give rise to networks that on a small scale look largely random” (515). And as he predicts, I believe studying complex edge-preserving NMA rules will progress our understanding of such random evolving networks.
Keywords
Keywords
◼
Network Mobile Automata
◼
Network Evolution
◼
Ruliology
◼
Mobile Automata
◼
Cellular Automata
Acknowledgement
Acknowledgement
I would like to say a huge thank you to my mentors Mano Namuduri and Shivam Sawarn for guiding me through this project and always being present to help. Without them by my side, I would have gotten lost and stuck on many occasions. I would also like to thank Nik Murzin and Jonathan Gorard for their technical support in supplying me with functions dealing with Hypergraphs and readily adapting their code for my needs. Finally, I thank Stephen Wolfram and all the Wolfram Summer School staff for providing me with this project and supplying me with many resources to succeed.
References
References
1
.“Mobile Automata: A New Kind of Science | Online by Stephen Wolfram [Page 71].” n.d. Www.wolframscience.com. Accessed July 12, 2023. https://www.wolframscience.com/nks/p71--mobile-automata/.
2
.“Evolution of Networks: A New Kind of Science | Online by Stephen Wolfram [Page 508].” n.d. Www.wolframscience.com. Accessed July 12, 2023. https://www.wolframscience.com/nks/p508--evolution-of-networks/.
3
.“Note (G) for Evolution of Networks: A New Kind of Science | Online by Stephen Wolfram [Page 1040].” n.d. Www.wolframscience.com. Accessed July 12, 2023. https://www.wolframscience.com/nks/notes-9-12--network-mobile-automata/.
4
.“Hypergraph | Wolfram Language Paclet Repository.” n.d. Resources.wolframcloud.com. Accessed July 12, 2023. https://resources.wolframcloud.com/PacletRepository/resources/WolframInstitute/Hypergraph/.
5
.“EnumerateWolframModelRules | Wolfram Function Repository.” n.d. Resources.wolframcloud.com. Accessed July 12, 2023. https://resources.wolframcloud.com/FunctionRepository/resources/EnumerateWolframModelRules/.
CITE THIS NOTEBOOK
CITE THIS NOTEBOOK
The Ruliology of network mobile automata
by Joel Choi
Wolfram Community, STAFF PICKS, July 12, 2023
https://community.wolfram.com/groups/-/m/t/2959221
by Joel Choi
Wolfram Community, STAFF PICKS, July 12, 2023
https://community.wolfram.com/groups/-/m/t/2959221