Random Explorations in Automata Theory Gary J. Shannon Created: Mar. 14, 2003 Last updated: Mar. 14, 2003

Spin States: A Generalization of the Margolus Neighborhood

[Also see Cellular Automata Neighborhoods for more information.]

The Margolus neighborhood partitions the space of the CA into disjoint boxes consisting of 2 cells on a side.  That partitioning then changes from one clock tick to the next so that members of one box become joined to members of an adjacent box on alternate ticks. Figure 1 Illustrates the more clearly.

Fig 1. The two phases of the Margolus neighborhood.

In figure 1a the box boundries are drawn so that all the red cells (added just for clarification) and all the blue cells are grouped together, while in figure 1b, which represents the alternate half of the cycle,  the colored dots have remained stationary while the boundry lines were shifted by one sqaure in the diagonal direction so that the red and blue cells share boxes.

The other significant difference between the Margolus neighborhood and the conventional CA neighborhood is that the entire contents of the box is updated at once. All four cells change state based on the same rule which is written in a form such as that shown in figure 2.

Fig. 2. A portion of a typical
Margolus neighborhood rule.

The biggest advantage of the Margolus neighborhood is that rules can be written which conserve the total number of states so that they can be used to simulate real-life particles, molecules, or billiard balls without worrying that one of those billiard balls might suddenly vanish from the playing field.

On the other hand the drawback to the Margolus neighborhood, at least from an aesthetic point of view, is that the partitioning scheme is imposed artificially from outside the universe of the cells themselves. Of course the same thing could be said of the rules of any CA, but the rules are not only necessarily, but can at least be imagined to be inherent in the nature of the cell rather than imposed from the outside.  The Margolus partitions, however, are global and transcend the single cell making them seem more artificial. From the perspective of an inhabitant of the grid they would seem quite otherworldly and mystical, having no relationship to the "real" things like cells and states.

Spin States

There is, however, a different way to visualize the Margolus neighborhood which makes it a property of the cells themselves, rather than something external to the cells.  Consider the Margolus neighborhood of figure 1 as redrawn in figure 3a and b.

Fig. 3. The Margolus neighborhood reconceptualized from inside the cells.

As indicated by the arrows each cell exists in a standard Moore neighborhood but is only able to see three of its neighbors at a time. Which three depends on which direction the set of three arrows is pointing. This direction is the spin state of the cell. From one clock tick to the next the spin state rotates by 180 degrees bringing a different set of neighbors into view.  By comparing the diagram of the Margolus neighborhood you will see that the neighborhood of the cell with spin states is identical.

All that remains is to rewrite the Margolus block rules as rules that can be applied to an individual single cell. First we will number the spin states as shown in figure 4.

Fig. 4. The four spin states.

Next we assign new state numbers depending not only on the numerical state of the cell (0 or 1) but on the spin state of that cell as well.  These could be written as states 0 through 7, but for convience we will partition the numerical state portion of the state number from the spin state portion and write the complete state of the cell as the ordered pair <p,s> where p is the spin state and s is the numerical state from the original Margolus rule.  It should be remembered, however, that a pair such as <1,0> really represents a single state in that cell rather than two seperate states in a single cell.

The states in the Margolus rule can then be rewritten as shown in the example of figure 5.

Fig. 5. The states translated.

Now the rule of figure 6 can be rewritten as four rules, one for each of the four cells in the block.

Fig. 6. A Margolus rule.

We can see that the cell in the upper left hand corner is in numerical state 1 and spin state 0.  Further, we note that it has three neighbors consisting of, in clockwise order, cells in the states <1,1>, <2,1> and <3,0>.  Writing the rule as a list consisting of the state in the cell under consideration followed by the three neighboring states, and following that list with the new state to be assumed by that cell we arrive at the first rule:

{<0,1>,<1,1>,<2,l>,<3,0>} -> <2,0>

Note that the spin state of the new state of this cell is rotated by 180 degrees preparing it for the next tick when it will have a different neighborhood.  Rules for the remaining four cells can be derived in the same manner giving us the complete set of replacements for the single Margolus rule as:

1. {<0,1>,<1,1>,<2,1>,<3,0>} -> <2,0>

2. {<1,1>,<2,1>,<3,0>,<0,1>} -> <3,1>

3. {<2,1>,<3,0>,<0,1>,<1,1>} -> <0,0>

4. {<3,0>,<0,1>,<1,1>,<2,1>} -> <1,1>

It can be easily verified that this set of spin states under the set of rules derived in the manner described will behave identical to the equivalent Margolus neighborhood rule, but without recourse to anything that transcends the single cell and its local neighborhood.

Some Further Possibilities

Having duplicated the functioning of the Margolus neighborhood we can take a look at some of the things that spin states can do which a Margolus neighborhood cannot. There is no particular reason, except to mimic the Margolus neighborhood, for rotating the spin state of each cell by exactly 180 degrees with each clock tick.  The spin states could just as easily be rotated by 45, 90, or 135 degrees or more. Additional spin state numbers would have to be provided for the 45 and 135 degree rotations since the center arrow of the triple would no longer point at the diagonal neighbor and none of the existing state numbers reflect that fact.

If we allow variable rates of spin it must be decided whether all particles spin at the same rate or whether individual particles can spin at different rates.  The allowable rates of spin would range from 0 to 7, where 7 represent seven steps of 45-degrees, or equivalently, one step of 45-degrees in the counter-clockwise direction. The state descriptor would then be expanded to an ordered triple <r,p,n> where the new member r, represents rate of spin. Note that rate of spin could be invariant for a given cell or it could be changed as the result of the application of a rule.  Thus cells that started out spinning 45 degrees clockwise might, after a certain condition obtains, find themselves spinning at a rate of 90 degrees counter-clockwise.

This allows not only complex statically defined neighborhoods beyond the realm of the Margolus mechanism of partitioning, but allows for the evolution of the shape of the neighborhood over time, something never witnessed in either the conventional CA or the Margolus neighborhood CA. The cost of this power and generality is the proliferation of possible cell states. With 8 spin states and 8 rates of spin that can be applied to either one of two numerical states we would find that there are effectively 128 states in the simple 2-state automaton.  However that proliferation may well be worth the trouble if it results in new kinds of behavior not obtainable in any other manner.

Another variation on this theme is to alter the number of cells that a given cell can see, or to alter the relationships among the directions in the cell's field of view.  Figure 7 shows a few examples of other types of fields of view.

Fig. 7. A few sample
fields of view.

Bi-Directional vs. Directed Links

As soon as we allow spin states beyond the intital four, and spin rates beyond the intial fixed rate of 180 degrees per tick we face the situation where some of the field of view arrows will point at cells which do not reciprocate.  It will be the case that some cell A will be able to see some other cell B, but that B in turn will not be able to see A. The links are no longer bi-directional as is always assured in an ordinary CA, but become edges in a directed graph or matrix automaton. This creates the posibility for permanent or transient uni-directional loops around which states may propigate giving rise to novel behavior in the CA as a whole.  It remains to be seen what kind of behavior might emerge from this kind of cellular "froth" filled with shifting wormholes and loops.

Here are a few preliminary experiments with various view windows and spin rates.