Triangular Automata

The 256 Elementary Cellular Automata of the 2D Plane

Triangular Automata (TA) stands for cellular automata in the triangular grid. This Mathematica notebook introduces the topic while demonstrating the functionalities of the Triangular Automata package.
Download this notebook: https://github.com/paulcousin/triangular-automata-mathematica
More information: https://paulcousin.github.io/triangular-automata

Paul Cousin
https://orcid.org/0000-0002-3866-7615

Setup

Run the following command to import the package.

index_1.png

Introduction

Cellular automata in the triangular grid, or Triangular Automata (TA) for short, have already been studied in a few papers [1-17]. This work will focus on a natural subset of TA called Elementary Triangular Automata (ETA).

index_2.gif

ETA cells hold only binary states, each cell will thus either be:

“alive” and colored purple  index_3.gif, with a state  s = 1

“dead” and colored white  index_4.gif, with a state  s = 0


ETA rules determine the future state of a cell based on its current state and the states of its neighbors, regardless of their orientation. This results in only 8 possible local configurations. They can be plotted with TAConfigurationPlot.

index_5.png

index_6.gif

The package uses a graph-theoretical framework developed in a previous work on Graph-Rewriting Automata [20]. The triangular grid will here be considered as a graph. This graph must be expanded at each time step to simulate an infinite grid. The region of influence of a single cell grows in hexagonal layers. This is thus the most efficient way to expand the graph as well.

index_7.gif

It is useful to see the triangular grid as a graph because computing the evolution of ETA is made quite easy by properties of its adjacency matrix A and state vector S. Every vertex v of this graph will hold a state s(v). The neighborhood N(v) of a vertex is defined as the set of its adjacent vertices.

index_8.png            index_9.png

The configuration c(v) of a vertex is a number which, when they are indexed as we previously did, can be expressed as follows:

index_10.png

The space of possible ETA rules is finite. For each one of the 8 configurations, a rule must specify whether the vertex will be dead or alive at t+1. Consequently, there are only index_11.png possible rules. For this reason, ETA can be seen as the two-dimensional counterpart of Wolfram’s 256 Elementary Cellular Automata [18-19]. Furthermore, the triangle is the regular polygon tiling 2D space with the smallest number of neighbors per cell. ETA are thus the most basic 2D cellular automata and have a fundamental aspect in this regard.

Each rule R is a map from configuration space to state space.

index_12.gif

Each rule can be labeled by a unique rule number n. We will use the labeling system which was independently proposed in references [9] and [20], since it must be somewhat natural and because it has useful properties.

index_13.png

This system, inspired by the Wolfram code [18], is such that a rule number in its binary form displays the behavior of the rule. Starting from the right, its digits indicate the future state for each configuration as they have been ordered previously. Rules can be plotted with the TARulePlot function.

index_14.png

index_15.png
index_16.gif

Basic functions

Starting Points

Grids have a special format. They are captured in a list with three elements: a precursor of the adjacency matrix, a state vector and a coordinates vector. The first two are in the SparseArray format.

To simplify things, this package provides few starting points ready to use:

TAStartOneAlive: a grid with only one alive cell at the center

index_17.png

index_18.gif

TAStartLogo: a grid with a logo that contains all 8 local configurations.

index_19.png

index_20.gif

TAStartRandom[n]: a grid with cells that are randomly either alive or dead on n layers.

index_21.png

index_22.gif

Edit

The TAEdit function enables to edit a grid and copy the result.

index_23.png

index_24.png

Copy-paste the obtained grid:

index_25.png

index_26.gif

Evolution

We can evolve these grids with different rules using the function TAEvolve. Let’s try to evolve TAStartOneAlive with rule 181.

index_27.png

index_28.gif

As expected from the earlier plot of rule 181, the environment has become alive and we have three dead cells surrounding a central alive cell. It would be nice to see what will happen after that. The function TANestEvolve can be used to jump ahead several time steps. Let’s look at what TAStartOneAlive will look like after 64 time steps of evolution with rule 181.

index_29.png

index_30.gif

With this function, all the intermediate steps are lost and we only get the last grid. TANestListEvolve returns a list with all the intermediate steps.

index_31.png

index_32.gif

TAEvolutionPlot shows an animated version of what we have just computed.

index_33.png

index_34.gif

Behavior

In this section, a preliminary study of ETA is presented to motivate a future, more in-depth analysis. It is of particular interest to see what happens to a single living cell under different ETA rules so most of the following figures will come from this starting point.

Beauty

One of the most striking aspects of these automata is their aesthetic quality, which cannot be better illustrated than by a few selected examples.

index_35.png

index_36.gif

index_37.png

index_38.gif

index_39.png

index_40.gif

index_41.png

index_42.gif

Chaos

Given the existing literature on cellular automata, it is quite expected to see some of these rules behave chaotically. The example of rule 53 confirms it.

index_43.png

index_44.gif

Starting from two randomly generated 64 layers wide grids that are completely similar except for the central cell, the trajectories strongly diverge.

index_45.gif

index_46.gif

index_47.png

index_48.gif

index_49.png

Fractals

Some ETA rules produce remarkable scale-free structures.

index_50.png

index_51.gif

index_52.png

index_53.gif

index_54.png

index_55.gif

Space-Time

Similar to the way Elementary Cellular Automata [18-19] are most often represented, the evolution of an ETA can be displayed in one single plot. Here, an instant is two-dimensional, so adding the dimension of time creates a 3D structure. In these space-time plots, time flows downward. The successive grids are stacked beneath each other, starting from the initial conditions at the top. To avoid the infinite planes created by an alive environment, we can display only the cells that have the opposite state to it at each time step. A lot of information is therefore lost. We do not see most of the internal structure and we cannot know the state of the environment. Nevertheless, this representation helps visualize some properties of ETA that are difficult to notice otherwise. For instance, certain rules create 3D space-time fractals.

index_56.png

index_57.gif

These plots can be exported to 3D software like Blender with the following code:

index_58.png

index_59.gif

Self-Reproduction

As mentioned in reference [17], one of the original motivations for the development of cellular automata was to create a mathematical model of self-reproduction. Interestingly, 4 of the 256 ETA rules naturally reproduce any finite pattern given as initial conditions: rules 85, 90, 165 and 170. A proof of self-reproduction based on path counting already exists for rule 170 [17]. Similarly spirited proofs could probably be proposed for the others.

index_60.png

index_61.gif

Noise

Some rules seem to generate a pretty good noise. For example, if we pick a simple starting point without symmetries, rule 37 will usually turn it into an expanding disk with a random-looking interior.

index_62.gif

index_63.gif

index_64.gif

index_65.gif

Textures

Organic textures can be obtained by applying other rules to this pseudorandom grid.

index_66.png

index_67.gif

index_68.png

index_69.gif

index_70.png

index_71.gif

index_72.png

index_73.gif

Boring Rules

There is an identity rule which leaves any grid unchanged: rule 240.

index_74.png

index_75.gif

And a negative rule that swaps alive and dead states: rule 15.

index_76.png

index_77.gif

Twins

A simple procedure can be followed to find the evil twin of a rule that has the same effect but in the negative world. To find it, take the number in its binary form (with the leading zeros needed for the number to be 8 digits long), swap ones and zeros and read it backwards. Let us take rule 214 as an example.

First, find the binary form of the rule number:   index_78.png

then swap ones and zeros:   index_79.png

and finally reverse it:   index_80.png

Two functions help work in the negative world: TANegativeGrid returns the negative of a grid and TANegativeRule returns the number of the twin rule.

index_81.png

index_82.png

index_83.png

index_84.gif

index_85.png

index_86.gif

Final Thoughts

If you want to delve deeper into the mathematics behind this work, you can read the related paper: https://arxiv.org/abs/2309.15795

I hope you will enjoy this package. Share what beautiful or interesting things you find with it!

References

[1] R. W. Gerling, “Classification of triangular and honeycomb cellular automata,” Physica A: Statistical Mechanics and its Applications, vol. 162, no. 2, pp. 196–209, Jan. 1990.

[2] C. Bays, “Cellular Automata in the Triangular Tessellation,” 1994.

[3] K. Imai and K. Morita, “A computation-universal two-dimensional 8-state triangular reversible cellular automaton,” Theoretical Computer Science, vol. 231, no. 2, pp. 181–191, Jan. 2000

[4] L. Naumov, “Generalized coordinates for cellular automata grids,” in International Conference on Computational Science, Springer, 2003, pp. 869–878.

[5] C. Bays, “Cellular Automata in Triangular, Pentagonal and Hexagonal Tessellations,” in Encyclopedia of Complexity and Systems Science, 2009, pp. 892–900.

[6] Y. Lin, A. Mynett, and Q. Chen, “Application of Unstructured Cellular Automata on Ecological Modelling,” in Advances in Water Resources and Hydraulic Engineering, Berlin, Heidelberg: Springer Berlin Heidelberg, 2009, pp. 624–629. doi: 10.1007/978-3-540-89465-0_108.

[7] C. Bays, “The game of life in non-square environments,” in Game of Life Cellular Automata, Springer, 2010, pp. 319–329.

[8] B. Breckling, G. Pe’er, and Y. G. Matsinos, “Cellular automata in ecological modelling,” in Modelling Complex Ecological Dynamics: An Introduction into Ecological Modelling for Students, Teachers & Scientists, Springer, 2011, pp. 105–117.

[9] M. Zawidzki, “Application of Semitotalistic 2D Cellular Automata on a Triangulated 3D Surface,” Int. J. DNE, vol. 6, no. 1, pp. 34–51, Jan. 2011, doi: 10.2495/DNE-V6-N1-34-51.

[10] G. M. Ortigoza, A. Lorandi, and I. Neri, “ACFUEGOS: An Unstructured Triangular Cellular Automata for Modelling Forest Fire Propagation,” in High Performance Computer Applications, I. Gitler and J. Klapp, Eds., in Communications in Computer and Information Science, vol. 595. Cham: Springer International Publishing, 2016, pp. 132–143. doi: 10.1007/978-3-319-32243-8_9.

[11] M. Saadat, “Cellular Automata in the Triangular Grid,” 2016.

[12] S. Uguz, S. Redjepov, E. Acar, and H. Akin, “Structure and reversibility of 2D von Neumann cellular automata over triangular lattice,” International Journal of Bifurcation and Chaos, vol. 27, p. 1750083, 2017.

[13] M. Saadat and B. Nagy, “Cellular Automata Approach to Mathematical Morphology in the Triangular Grid,” ACTA POLYTECH HUNG, vol. 15, no. 6, pp. 45–62, 2018, doi: 10.12700/APH.15.6.2018.6.3.

[14] G. A. Wainer, “An introduction to cellular automata models with cell-DEVS,” in 2019 Winter Simulation Conference (WSC), IEEE, 2019, pp. 1534–1548.

[15] A. V. Pavlova, S. E. Rubtsov, and I. S. Telyatnikov, “Using cellular automata in modelling of the fire front propagation through rough terrain,” IOP Conf. Ser.: Earth Environ. Sci., vol. 579, no. 1, p. 012104, Oct. 2020, doi: 10.1088/1755-1315/579/1/012104.

[16] M. R. Saadat and B. Nagy, “Generating Patterns on the Triangular Grid by Cellular Automata including Alternating Use of Two Rules,” in 2021 12th International Symposium on Image and Signal Processing and Analysis (ISPA), Zagreb, Croatia: IEEE, Sep. 2021, pp. 253–258. doi: 10.1109/ISPA52656.2021.9552107.

[17] M. R. Saadat and N. Benedek, “Copy Machines - Self-reproduction with 2 States on Archimedean Tilings,” 2023.

[18] S. Wolfram and others, A New Kind Of Science, vol. 5. Wolfram media Champaign, IL, 2002.

[19] E. W. Weisstein, “Elementary Cellular Automaton”, [Online]. Available: https://mathworld.wolfram.com/ElementaryCellularAutomaton.html

[20] P. Cousin and A. Maignan, “Organic Structures Emerging From Bio-Inspired Graph-Rewriting Automata,” in 2022 24th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC), Hagenberg / Linz, Austria: IEEE, Sep. 2022, pp. 293–296. doi: 10.1109/SYNASC57785.2022.00053.

Created with the Wolfram Language