[znqcsgwy] Best cellular automaton with von Neumann neighborhood

"Best" is of course subjective.  We probably want cellular automata supporting stable local structures, but also spaceships for occasional long range interactions (New Kind of Science).  (Also previously on "mostly local" cellular automata.)

The von Neumann neighborhood is attractive because it is well defined on manifolds of squares connected through edges in arbitrary ways, for example, the surface of a polycube.

(In contrast, Conway's Game of Life uses the Moore neighborhood of 8 neighboring cells: 4 edge-adjacent orthogonally and 4 vertex-adjacent diagonally.  If the manifold is not Euclidean, then there may be cells with a diagonal neighbor missing (e.g., at the corner on the surface of a cube), or they may have more than 1 diagonal neighbor through a vertex (e.g., fit 5 squares around a point in hyperbolic space).  How should a cellular automata rule for flat space be adapted for those cells?)

Hypothetically, for a simple hardware implementation, the Moore neighborhood would require crossing wires but von Neumann would not.  (But distributing clock and power in von Neumann will require wire crossings.)

We enumerate the number of possible rules.

Assume totalistic (more precisely, outer-totalistic) rules, which are isotropic.

40 2
31 2
22 1

5 possibilities, and state of center square also matters, so 10 rules.  Empty cell surrounded by empty neighbors should stay empty, so 9 rules.  2^9=512 possibilities.  (This is very similar to counting the number of possible Boolean functions of a given number of inputs.)  These have probably all been explored.

Probably other reductions possible: e.g., swap black and white.

Slightly more sophisticated than totalistic: if exactly two neighbors of same color, the same colors can be across from each other (180 degrees apart), or separated by 90 degrees.  Then, 6 12 11 yields 2^11 = 2048 possibilities.

We could go even less isotropic: up and down are distinguished but left and right are not.  We do not explore this.  There will be problems on manifolds where distinguishing directions is not possible.

I suspect a von Neumann neighborhood with 2 states per cell is not enough for anything interesting on par with Conway's Game of Life, because someone would have discovered and publicized it already if it is possible.  Therefore, we consider 3 states:

400 3
310 6
220 3
211 3

15 possibilities, plus center cell so 45, then 44.  3^44 possibilities.

If not totalistic but distinguishing splitting versus adjacent: 3+6+6+6=21 63 62 = 3^62 possibilities.

More reduction based on colors definitely possible.

Work by others:

Serizawa, T. (1987) Three-State Neighbor Cellular Automata Capable of Constructing Self-Reproducing Machines. DOI: 10.1002/scj.4690180404.

via the Conway Life Wiki.

Hexagon tiling and triangle tiling also possible.