Sunday, January 17, 2016

Graph of commuting elementary cellular automata

In one of the previous posts, I wrote about pairs of commuting elementary cellular automata. Two cellular automata rules A and B commute, if result of applying them to the universe does not depend of application order:

$$A(B(x)) = B(A(x)).$$

As I wrote previously, such commuting pairs can be seen as a single automaton in the universe, where time has two dimensions.

However, the visualization I used (binary image 256x256) was not very clear. How to draw it better? Of course, draw it as a graph! Here are the results.

All automata

The graph below displays relations between almost all automata. It excludes automata 170 (shift leftward), 204 (identity), 240 (shift rightward) that commute with every other automaton; their binary complements (15,51,85) and trivial automata 0 and 255, that commute with half of all elementary automata. Also, to reduce clutter, single nodes: automata that do not commute with any other, were also excluded from the graph.

Commuting elementary automata map. Nodes are automata, edges show commutation. Yellow: even rules, red: odd rules.

The graph data was generated with simple python script, and then semi-automatically laid out using the yEd graph editor.

This graph reveals some interesting features. First, it have two mirror symmetries. On this layout, horizontal flip corresponds to mirroring automata, and vertical flip corresponds to binary complement (automaton, working on inverted field).

Additive automata are seen as compact groups of nodes, where each node in the group is connected with each other.

Even automata

My simulator only supports even elementary automata: the ones that preserve emptiness of space, transforming empty universe into empty. Odd rules are opposite: they invert state of the universe filled with zeros. Odd automata are shown as red nodes in the first graph. If only yellow nodes are left, graph simplifies:

This graph have no complement symmetry.