Cyclic cellular automaton with 3-neighborhood

Question

Consider a 2D cyclic cellular automaton with randomized starting states and the usual von Neumann 4-neighborhood ruleset. It is well-known that this CA produces a stable and periodic state after a few hundred iterations. Yet removing just one element of the neighborhood (upper, left, right or lower cell) from the iteration ruleset, thus creating a 3-neighborhood, typically results in a sequence that rapidly approaches a static and disordered state within a few dozen iterations. It's as if the neighborhood used in the iteration ruleset must completely surround the target cell in order for standing waves to form amongst the cells. Is there an explanation for this behavior with a 3-neighborhood?

Answer 1

In two or more dimensions, the long-term behavior of cyclic cellular automata tends to be dominated by clusters of cells called "demons", which consist of a closed loop of adjacent cells, with each cell in the loop having a state one step further in the cycle than the previous cell.

The cells in such a loop will always increment their state on every time step, which implies that the loop cannot be destroyed by external effects (since no outside influence can prevent the cells from changing their state the way the loop structure forces them to). As a side effect, such loops will also emit periodic spiral waves traveling outwards from the loop core, which will eventually drive the entire lattice to oscillate with a period equal to the number of states in the cycle.

However, for such a demon loop to form, the neighborhood relation of the underlying lattice must admit a closed loop of cells, each of which is a neighbor of the previous one. The three-neighbor lattice formed by removing one cell from the four-neighbor von Neumann neighborhood has an asymmetric neighborhood relation that does not admit such closed loops!

For example, if we remove the left cell from the neighborhood, so that no cell is counted as a neighbor of the cell immediately to the right of it, then it turns out that no cell can be a neighbor of any cell on any columns to the right of it on the lattice. Thus, a chain of successive neighbors starting from a given cell can only extend up, down or to the right of the original cell, but never to the left of it.

And, in particular, since a non-self-intersecting chain of more than two neighboring cells cannot loop back to its starting point while staying within a single column (i.e. moving only up or down), it follows that such a chain must at some point extend at least one cell to the right in order to form a closed loop. And once it does, it can no longer go back left, since cells on your three-neighbor lattice have no left neighbors!

Thus, no demons can form on such an asymmetric lattice. What you get instead is something similar to one-dimensional cyclic CA dynamics within each column, but perturbed by the one-way influence from each column to the one on its right side.

You should also obverse a similar effect e.g. if you start with the eight-cell Moore neighborhood and remove any three adjacent cells from it (either one full side of the square or one corner with its adjacent neighbors will work) to obtain an asymmetric five-cell neighborhood. In three or more dimensions, however, just removing all cells on one side of a central plane from the neighborhood will not be sufficient, since demons can still form within the plane. Also removing one half of the neighbors within the plane will work, though.

In general, a sufficient and necessary condition for a cyclic CA to support demons is that its neighborhood graph must contain a directed cycle whose length is an integer multiple of the number of states in the automaton. In turn, a sufficient (but not necessary) condition for the non-existence of such a cycle is that the lattice can be somehow divided into one-dimensional lines of cells (where each line can only contain neighbor cycles with fewer cells than the CA has states), and these lines partially ordered in such a way that cells in each line can only have neighbors within that line itself and in lines that follow it in the order.