Obviously, a cool thing to do whould be to enumerate all these particles and understand their interactions
To do this, we can do the following:
Start with some initial condition
Find “connected components”, that is parts of the initial condition which are far enough so that they will not interact in the next CA step
Perform a CA evolution on each of these components separately
Find “connected components” of the evolution result
Make edges from the initial particles to every component of its evolution result. These edges represent the “decay” hierarchy of that particle
Do this for many initial conditions and make a network which describes the interactions of particles in the system
Generating all possible initial conditions
We need a normalization function which would rotate and reverse the particles in a particular form so that we would avoid duplicates
The most size we can do in reasonable amount of time is 3.
Searching for particles in a state
The distance between particles should be at least 2 so that they cannot interact at the next step
Selecting particles from interaction network
The network generated in the previous step is kind of messy though, because it includes all intermediate states, which are impossible to generate by particle interactions, or which eventually annihilate all by themselves.
To do that, we can repeat removing vertices which have no in- or out-edges, until we reach a fixed state.
Extra fun examples
Particle which doesn’t move
Particle which doesn’t move and produce more particles
I wonder if something similar can be done with network systems…
The ultimate goal of my project is to figure out the computational system which reproduces the known Universe.
There are two aproaches to that:
That’s what everyone in the physics community is doing. The idea is to reverse-engineer the laws of physics. You look at the World, and try to understand the simple principles which determine how it works.
That’s what my project is about. The idea is to enumerate simple systems, find ones which behave in an interesting manner, and then find ones which reproduce the known laws of physics.
The problem with this approach, of course, is that there are many orders of magnitude between fundamental Planck scale, and the energy scale achievable in modern experiments:
Networks seem to be the most apropriate class of models to think about.
Even though all universal computational systems are ultimately equivalent, some computations are more naturally represented in certain systems.
The networks are interesting because they are the most structureless systems which nevertheless preserve the notion of locality (or “closeness” of elements).
The networks might be more complicated though than ordinary graphs.
In particular, the system we are interested in should contain a set of tuples of vertices, and both tuples and vertices might be labeled and have their elements numbered.
Such generalizations of graphs include:
Numbered graphs (networks, in which outgoing edges from a particular node have inequivalent indexes)
Oriented graphs (networks, in which outgoing edges from a particular node have order associated with them)
Networks with arbitrary discrete symmetry groups attached to their vertices
Oriented networks (both in hypergraph, numbered, oriented, etc. cases)
Networks which have integers arrached to vertices or edges
The kind of networks studied in my project are trivalent oriented graphs, meaning that the edges outgoing from a given vertex have particular order.
Oriented graphs are chosen because they seem to be the most natural kinds of networks to represent planar graphs, and planar graphs are chosen because they are easier to visualize and therefore easier to understand.
Of course, other kinds of networks ought to be considered in the future.
Each vertex of an oriented graph is attached to three indexed edges, for example:
Also, there are graph ports to specify the boundary conditions, which represent the border of the part of the network, which is known. Graph ports are very useful for specifying rewrite rules (which will be described later).
OrientedGraph can be constructed by specifying the list of edges:
You can see that if we change the edge ordering for the first vertex, the resulting graph will be different
There potentially might be many different ways to do evolution of such systems.
In my project I was studying network rewrite systems, evolution of which constists of 3 steps:
Find a subnetwork in a graph isomorphic to rule〚1〛
Delete this subnetwork converting new orphant edges to graph ports
Insert the rule〚2〛 to the network preserving the ordering of graph ports (the number of graph ports should be the same for rule〚1〛 and rule〚2〛)
For example, for the rule rewriting singular vertices into triangles:
we can get a nested structure as an evolution result:
The vertices in the network have indexes, the rule is always applied to the smallest index, and the new vertices are appended so that after the evolution step their indexes are the largest.
In this project deterministic systems were studied (so that no matter in which order the rules are applied the result of evolution is always the same).
That was ensured by using non-self-overlapping left sides of rules (so that for any vertex in a network, there is at most one possible way to apply the rule which envolves this vertex).
Using such rules ensures determinism, however one should keep in mind that it is not a required condition for determinism.
The singular-to-triangle rule shown above is deterministic. Other examples of deterministic rules include:
In order to explore the network systems, we need to enumerate the networks first.
The counts of networks depending on their vertex count and graph ports count are the following:
Examples (all networks with 3 vertices and 3 graph ports):
Only planar and with singular boundary
In this project, however, I only studied planar networks, so if we remove all the networks which are not planar, and also which have more than one boundary, we get the following counts:
Examples (all planar networks with 4 vertices and 4 graph ports):
Only planar, with singular boundary and non-self-overlapping
In order to enumerate the rules, we will also need networks, which are non-self-overlapping. The counts of planar and non-self-overlapping networks are the following:
You can see that there are not very many networks which are non-self-overlapping.
In fact, there are only 14 + 1 + 6 == 21 with 3 graph ports or more.
Examples (all non-self-overlapping planar networks with 7 vertices and 3 graph ports):
Same number of vertices in left and right sides
Here are counts of planar deterministic rules
As you can see, planar deterministic rules only appear if the number of vertices is about twice as large as the number of graph ports.
Examples of rules with 7 vertices and 3 graph ports:
Examples of rules with 8 vertices and 4 graph ports:
Different number of vertices in left and right sides
One interesting example is 1 7 rules with 3 graph ports:
Planarity testing turned out to be amazingly simple.
If this formula does not hold (that is when faceCount is smaller than given value), graph is not planar.
This can be proven by induction. Imagine we allow graphs with arbitrary vertex degrees for a moment. Then we can construct graphs by adding edges one-by-one. When we add an edge, one of 3 things happens:
New vertex is added
A single new face is added
A face is removed (some thought required to understand this one, but the key idea is that in this case an edge starts in one face, and ends in another. It is easy to see by drawing a picture, that these two faces will merge after adding an edge)
There is no way to add more than one face by adding only one edge. Once neither vertex nor face is added with new edge, the formula for planar graphs is violated, and this can never be restored.
It is fairly easy to make a particle which moves in one direction on a uniform grid without leaving any traces behind:
2D particles require the grid and the particle itself to be anisotropic.
The reason for this is that the rule should partly contain the particle, and partly the fragment of the grid. If either grid or particle would be isotropic, the rule will become self-overlapping.
One way to construct such a grid is demonstrated below:
Unfortunately, RodElectricalEmbedding (analog of SpringElectricalEmbedding, which takes care about edge ordering) takes too much time to compute for large grids, so I use SpringElectricalEmbedding instead, and highlight the particle, so that it is possible to see it.
If you look carefully enough, you can see particle propagating through the grid (notice that SpringElectricalEmbedding might flip the graph upside-down sometimes), and leaves a trace behind it.
No interacting particles
Because rules are required to be non-self-overlapping, it is not possible to make particles interact in a trivial way.
The reason is that the collision location is undefined. The rule might be either applied to move one particle or another, and depending on the relative counts, particle might collide in different places, which seem to be violating determinism of the system.
No complete non-overlapping basis
One thing that one can imagine would be good to have is a complete non-overlapping basis of rules.
Non-overlapping means that rules not only don’t overlap with themselves, but also don’t overlap with other rules, so that for any place in the network at most one rule can be applied.
Complete means, that exactly one rule should be possible to apply at any place in the network.
The benefit of such system is that it doesn’t require one to search through the network for subnetworks, which seems more natural.
However, it turned out that such complete non-overlapping bases can only produce nested behavior.
Indeed, with such a basis of networks, any network can be partitioned into the subnetworks from the basis.
Then, when one of the rules is applied, the part of the partitioning changes, but all the other parts stay the same.
Therefore, the borders between different subnetworks in the partitioning can never change.
The requirement of rules to be non-self-overlapping seems to limit the complexity of behaviour of such systems too much, for instance, preventing appearance of simple particle interactions in the network.
However, particles might still appear as some kind of collective effect.
For one thing, it seems to be necessary for particles to interact with the grid, and leave traces behind in order to interact with each other.
Which means, that it might not be possible to construct particle without introducing quantum mechanics.
Quantum mechanics in turn is not local, therefore, it cannot appear in planar network rewrite systems, which means that we should start looking into non-planar systems in the future.
What is the smallest rule required to have a class-4 network system?
Is it possible to produce particles in other kinds of networks, such as hypergraphs, numbered graphs, or graphs with vertex labels?
How to produce particles in non-planar networks?
Are there network evolution systems other than network rewrites?
Stephen Wolfram. A New Kind of Science, Chapter 9.