Deterministic Planar Network Systems

Name: Maksim Piskunov

Instructor: Todd Rowland

Wolfram Science Summer School 2015

http://maxitg.com/physics/DeterministicPlanarNetworkSystems.nb

Homework Solution

◼

Specification

ruleDescription[ruleNumber_] := Reverse[IntegerDigits[ruleNumber, 3, 19]]

rule=1131956414;

ArrayPlot@{ruleDescription[rule]}

initRandom[fieldSize_Integer] := Block[{}, SeedRandom[1131956414]; Table[RandomInteger[{0, 2}], {fieldSize}, {fieldSize}]]

caEvolution[init_, steps_] := caEvolution[init, steps] = CellularAutomaton[{rule, {3, 1}, {1, 1}}, init, steps];

stateManipulate[ruleNumber_, init_, steps_, options___] := Manipulate[ ArrayPlot[caEvolution[init, steps]〚i〛, options], {{i, 1, "Step"}, 1, steps, 1}, SaveDefinitions  True ]

sliceManipulate[ruleNumber_, init_, steps_, options___] := Manipulate[ ArrayPlot[caEvolution[init, steps]〚All, i〛, options], {{i, 1, "Position"}, 1, Length @ init, 1}, SaveDefinitions  True ]

◼

From random initial conditions

stateManipulate[rule,initRandom[200],200]

Step

You can clearly see particles moving around in this slice:

sliceManipulate[rule,initRandom[200],200]

Position

◼

Single particles

Let’s look at individual particles in this system.

▼

Speed-of-light particle with 2 phases

manualParticles[1]=

2	1	0
2	2	1
2	2	0
0	0	2

;

stateManipulate[rule,ArrayPad[manualParticles[1],{30,20},2],200]

Step

▼

Particle which produces other particles

Which then collide and annihilate

◼

Collisions

The things get more exciting when you collide particles

▼

Annihilation

Sometimes particles just annihilate

▼

Producing more particles

Sometimes collision produces different particles

▼

Big Bang!

But sometimes, collisions produce complete mess, eventually filling the whole space with interacting particles

◼

Automated Particle Discovery

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

▼

Decay network

▼

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 Objective

The ultimate goal of my project is to figure out the computational system which reproduces the known Universe.

There are two aproaches to that:

Top  Down

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.

Bottom  Up

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:

◼

Why networks?

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:

Hypergraphs

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

◼

OrientedGraph

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

◼

Rewrite system

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.

◼

Deterministic systems

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:

Code

Visualizations

◼

Network Enumeration

In order to explore the network systems, we need to enumerate the networks first.

▼

All networks

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):

◼

Rule Enumeration

▼

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

Counts:

One interesting example is 1  7 rules with 3 graph ports:

Main Results

◼

PlanarQ

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.

◼

1D particle

It is fairly easy to make a particle which moves in one direction on a uniform grid without leaving any traces behind:

▼

Rule

▼

Initial condition

◼

2D particle

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:

▼

Rule

▼

Initial Condition

▼

Evolution

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.

Network systems

Network rewrites

Oriented graph

Conclusions

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?

Links/References

Stephen Wolfram. A New Kind of Science, Chapter 9.

Maksim Piskunov. Planar Network Systems, Wolfram Science Summer School 2014 project, https://www.dropbox.com/s/refm2zwk418ow64/ProjectNotebook.nb?dl=0

Graph

Network

Network systems

Network rewrites

Oriented graph

Physics

Fundamental Physics

Other

Last Modified: Thursday, July 16, 2015