2
$\begingroup$

So in the little I know about formalization of cellular automata, it appears there are 4 major categories of cellular automata:

  1. 1-dimensional (cellular automata on the line)
  2. 2-dimensional (cellular automata on the plane)
  3. 3-dimensional (cellular automata in the cube)
  4. hyperbolic cellular automata

In the plane example, there are 3 main tilings: the square tiling, triangular tiling, and hexagonal tiling, which seem to have been well studied. I am not sure about the 3D case yet. I have the book on Cellular Automata in Hyperbolic Spaces but haven't worked fully through it.

But it seems that the general model is a bunch of nodes/cells with links between them. I can imagine not just these regular grids/tilings, but cases where you have say 5-link cells connected to a bunch of 7-link cells, connected to a bunch of 4-link cells. The 7-link cells play a 7/8 musical rhythm, the 5-link cells a 5/8 musical rhythm, and the 4 a 4/4 musical rhythm. Then you see what patterns evolve out of that, or how they interact. Or those serve as input signals to another simplified cellular automaton which evolves.

Basically I'm wondering what work has been done on the generalization of cellular automata to beyond these 4 categories, and where I can learn more.

$\endgroup$
1
3
$\begingroup$

Cellular automata can be defined on Cayley graphs of arbitrary groups. Intuitively, the states go on the nodes of the graph, and the neighborhood of a node is defined using the edges. The $d$-dimensional case corresponds to the group $\mathbb{Z}^d$ with edges $(\vec v, \vec v \pm \vec e_i)$ for all nodes $\vec v \in \mathbb{Z}^d$ and the standard basis vectors $e_1, \ldots, e_d$.

Some very interesting results have been proved in this setting, with connections to geometric group theory, abstract algebra, and ergodic theory. Many results from classical CA theory generalize to CA on groups, but others only hold on some specific subclasses of groups. The book Cellular Automata and Groups by Ceccherini-Silberstein and Coornaert is a good resource on the topic.

$\endgroup$

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.