Metamaterial: 31 state Von Neumann neighborhood CA

[period54]

Hello!

I have been exploring a certain large family of cellular automata that, in a sense, generalize order statistics. The core idea is that we can construct a cellular automaton in which the transition function is simply the minimum of the inputs. Such a minimum CA is not very interesting on its own, but it has a number of curious features:

1. It is "as symmetric as possible". In other words, it is compatible with every symmetry of the underlying space. It doesn't even distinguish the central cell from its neighbors.
2. It can be extended to any number of states.
3. Every transition replaces the central cell with one of its neighbors. (Here I consider the central cell to be its own neighbor.)
4. As a consequence, if there are M distinct states present at generation N, there will be M or fewer states present at all future generations.
5. The number of times a particular state appears in the neighborhood is irrelevant; the rule only looks at whether it is present or not.
6. The rule is equivariant with addition: if you treat cell states as integers, adding N to each neighbor and applying the rule produces exactly the same result as applying the rule first, and then adding N.
7. As a consequence, there is no distinguished state. All states are, in a sense, equal, and the behavior depends on their relationships rather than absolute values.

These properties follow directly from the properties of the minimum function. It might appear as if only something like the minimum CA can hope to satisfy all of them, but this is not the case. You can construct an infinite number of such rules by first constructing a choice function that maps every zero-containing subset of states to an arbitrary element of that subset. This function can then be extended to a full transition function by collecting all the neighbors into a set, and using equivariance to find the value that should be assigned to it.

Even more is possible. One idea is to generalize the equivariance condition to equivariance under the (transitive, faithful) action of some group. This introduces a slight complication, because if our group contains an element of order n, where n is less than or equal to the maximum number of distinct neighbors the underlying space permits, then there will be a set unchanged by the action of that element, creating an ambiguity that makes the decomposition above no longer possible.

The simplest way to ensure that we don't run into such issues is to use a cyclic group of order p, where p is a prime larger than the maximum number of distinct neighbors.

Metamaterial (see attachments) is one of the most striking cyclically equivariant rules that I've stumbled upon. It combines small-scale dynamics characteristic of "ordinary" cellular automata, with spiral patterns that are common in CAs of similar general structure (RPS, cyclic CAs), and unusual large-scale patterns that move and change in a smooth, semi-continuous way. I have not seen such large-scale behavior in other kinds of CAs.

metamaterial_example.png (40.48 KiB) Viewed 1745 times

Due to the large number of states, the .rule file is massive (~4MB), and it takes Golly some time to load it. There's no designated "dead" state in this rule, so you should not run it without boundary conditions.

Code: Select all

Metamaterial:T200

works well, but Golly struggles with larger worlds or long steps.

The rule was generated by this script, which samples equivariant rules randomly. I don't remember the exact distribution I used, but the values in the script seem close enough, and they produce interesting results quite consistently.

There are other ideas worth exploring in this space. I have some experiments (in shadertoy) that keep the "extinction" rule, as well as full symmetry, but are not generally equivariant or indifferent to multiplicity. They generally don't translate into Golly very well: most of them require an unfeasibly large number of states to consistently display interesting behaviors.