2
$\begingroup$

Is there any cellular automaton on the Eisenstein integers? By this I mean that the triangles formed by the Eisenstein integers are considered as cells and each triangle has three neighbours plus itself. I programmed in python such a cellular automaton and am curious what properties it has.

git: https://gist.github.com/githubuser1983/aaea24744998f3b263519048136ee49d

video: https://www.youtube.com/watch?v=R_kcuWfGsTo

The only rule is: If a cell has exactly one alive cell in the neighbourhood then it is alive, otherwise it is dead.

Thanks for your help.

Edit: It seems that these triangular CA have been studied by : https://wpmedia.wolfram.com/uploads/sites/13/2018/02/08-2-4.pdf

$\endgroup$
2

1 Answer 1

3
$\begingroup$

Yes, such cellular automata have been studied. However, you're unlikely to find much about them using terms like "Eisenstein integers", since the convention in the field is to describe cellular automata on regular lattice using the lattice symmetry (e.g. hexagonal / rectangular / triangular for 2D lattices) and the neighborhood size and shape (i.e. how many and which nearby cells on the lattice can influence the behavior of the cell we are looking at).

For example, the triangles between Eisenstein integers form — unsurprisingly — a triangular lattice in the complex plane, and the three directly adjacent neighbors of a cell in this lattice constitute what is sometimes called the triangular von Neumann neighborhood (by analogy with the four-cell von Neumann neighborhood on the 2D square lattice).

One notable issue with cellular automata on this lattice is that the small neighborhood size rather severely limits the number of possible rules. In particular, with two states per cell, there are only $2^{2^4} = 2^{16}$ possible rules, even including non-isotropic rules — some of which will be isomorphic to each other, restricting the rule space even further.

While this does mean that an exhaustive enumeration and investigation of all CA rules on this neighborhood may be at least somewhat practical, it does also mean that some interesting behaviors found in cellular automata one larger neighborhoods may be missing from small neighborhoods like this simply due to the limited diversity of the rule space.

The small neighborhood — and, in particular, the fact that adjacent cells have disjoint neighborhoods — also limits the behavior of the edges of localized patterns. In particular, it should fairly easy to prove the following lemma (which also holds for the classic four-cell von Neumann neighborhood on the square lattice):

Lemma: If the all-dead lattice state is stable (i.e. a dead cell with zero live neighbors remains dead), then a finite pattern of one or more live cells on an unbounded lattice must either remain confined within a bounded region of the lattice, unable to escape it, or expand infinitely in all directions at the maximum possible speed.

(I may add a more detailed proof sketch later, but the basic idea is to consider the smallest axis-aligned hexagon covering all the live cells, and look at what happens to cells immediately outside each edge of this hexagon.)

In particular, this implies that totalistic CA rules on such a neighborhood cannot support spaceships, as found e.g. in Conway's Game of Life, since such a pattern must be able to expand indefinitely on one side while shrinking and not expanding on other sides. As interactions between spaceships (and stationary objects) are the main source of computational complexity and universality in Conway's Game of Life, any attempts to find computationally universal rules on the (triangular) von Neumann neighborhood are unlikely to succeed, at least not using the same methods.

That is, of course, unless one "cheats" by breaking some of the assumptions of the lemma above, e.g. by considering rules where the all-dead lattice state is not stable (but rather oscillates between all-live and all-dead), or initial states where the lattice is (mostly) covered in some non-uniform repeating pattern of cells. Then spaceships and other non-explosively propagating patterns may be possible. (At least they exist for the 4-cell von Neumann neighborhood, so I see no obvious reason why they couldn't also exist here.)


Addendum:

There are $2^{2 \times 4} = 256$ possible 2-state semitotalistic CA rules (i.e. rules where the new state of a cell depends only on its current state and the number of neighboring cells in each state) on your 3-neighbor lattice. (In fact, this is also the number of isotropic rules on your lattice, as all such rules — and indeed all rules that are invariant under a 120° rotation — on your lattice are semitotalistic.)

Since the adjacency graph of your lattice is bipartite, those rules come in exactly $128$ isomorphic pairs related either by state reversal (i.e. swapping the live and dead states) or, for the $2^4 = 16$ rules that are invariant under state reversal, "checkerboard reversal" (i.e. toggling the state of the cells in one half of the bipartition of the adjacency graph).

Let's try to classify those 256 (effectively 128) rules based on how finite patterns can propagate on the lattice. For brevity, I'll use the shorthand notation "B$n$" to indicate that a dead cell with $n$ live neighbors will become live, and "S$n$" to indicate that a live cell with $n$ live neighbors will remain live under the rule:

  • As noted, rules without B0 are subject to the lemma above, and so:

    • in rules without either B0 or B1 finite patterns of live cells cannot expand outside their bounding hexagon;

    • in rules with B1 but no B0 any finite pattern of live cells surrounded by dead cells will "explode", expanding in all directions at one cell per step.

  • In rules with both B0 and S3 any initial all-dead lattice state will flip to all-live and stay that way. All such rules have isomorphic state-reversed equivalents with neither B0 nor S3 (and which are thus subject to the lemma given earlier).

  • In rules with B0 but not S3, an initial all-dead state will flip indefinitely between all-dead and all-live. These rules are not subject to the lemma above, and are thus in principle capable of having spaceships. However:

    • In rules with B0 and B1, and neither S2 nor S3, finite patterns of live cells on an all-dead background (or vice versa) are still confined to their bounding hexagon.

    • In rules with B0 and S2, and neither B1 nor S3, finite patterns still expand explosively at one cell per step.

    • Rules with B0 and neither B1, S2 or S3 are state-reversal isomorphic to rules with B0, B1, S2 but not S3. Thus, only one of these two sets of 16 rules needs to be considered further.

Thus, there are only 16 (isomorphic pairs of) rules on your lattice that are, even in principle, capable of having spaceships. Of course, not all of them actually do.

For example, the rule B0/S (i.e. where all live cells die, and dead cells become live only if they have no live neighbors) has trivial dynamics where every finite pattern eventually settles into a period-2 cycle (and so does its state-reversed dual B0123/S012, where all dead cells become live, and live cells die only if they have no dead neighbors).

I haven't investigated the remaining 15 rules to see what kind of dynamics they support. Based on my experience of investigating rules with spaceships on the 4-cell von Neumann neighborhood many years ago, however, I'd probably start by looking at rules that are "nearly linear", i.e. close to the rule B02/S13, where cells switch state if and only if the have an even number of live neighbors.

Of course this rule itself cannot support spaceships, as it has both B0 and S3. (It instead displays universal linear replication, which is a neat phenomenon but ultimately useless for complex dynamics, as patterns never interact except by trivially passing through each other.) But if you drop S3, you get B02/S1, which is in the space of potentially spaceship-supporting rules, and would seem like a prime candidate for exploration to me. (Of course, this is just a semi-informed guess.)

$\endgroup$
3
  • $\begingroup$ thank you for your detailed answer. very helpful. $\endgroup$ Jun 13, 2022 at 18:21
  • $\begingroup$ @mathoverflowUser: BTW, I added a quick attempt at classifying the semitotalistic rules on your lattice with regard to the potential to support spaceships, based on some earlier similar investigation I did for the 4-cell von Neumann neighborhood. Just pinging you here since question authors don't otherwise get notified about answer edits. $\endgroup$ Jun 15, 2022 at 11:11
  • $\begingroup$ Thanks. I have experimented with different rules, but they seem to not escape the premises of your lemma, so they either expand indefinitely in all directions or stay bounded in some limited region. It would be cool to find some rule which is capable of producing some glider. I guess, I will have to program a user interface to choose some configuration based on your insight in this question. If you are comfortable with python and sagemath, and want to give it a try yourself, here is the code: gist.github.com/githubuser1983/aaea24744998f3b263519048136ee49d $\endgroup$ Jun 15, 2022 at 17:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.