Visualizing computation in large-scale cellular automata

Abstract

Emergent processes in complex systems such as cellular automata can perform computations of increasing complexity, and could possibly lead to artificial evolution. Such a feat would require scaling up current simulation sizes to allow for enough computational capacity. Understanding complex computations happening in cellular automata and other systems capable of emergence poses many challenges, especially in large-scale systems. We propose methods for coarse-graining cellular automata based on frequency analysis of cell states, clustering and autoencoders. These innovative techniques facilitate the discovery of large scale structure formation and complexity analysis in those systems. They emphasize interesting behaviors in elementary cellular automata while filtering out background patterns. Moreover, our methods reduce large 2D automata to smaller sizes and enable indentifying systems that behave interestingly at multiple scales.

Animations from the main paper

Figure 3: Side-to-side comparison of a CA simulation and its coarse-grained version. The first simulation is 256 × 256 cells and the second has been coarse-grained to 64 × 64. Notice the interesting patterns on Figure 3a are hardly distinguishable. They are highlighted by histogram-based coarse-graining in Figure 3b.
Base grid.
Coarse-grained.

Figure 9: Changing CA dynamics at multiple scales. 9a is a single glider, oscillating between 3 positions. They emerge spontaneously from a random initialization of a small grid as shown in 9b. When scaling the grid up, trails of gliders begin to appear, creating moving straight and diagonal lines (9c). Going a level higher, single gliders aren’t visible anymore (9d). The grid had to be coarse-grained to 256×256. In an even larger grid (9e), many more triangular-shaped waves travel and collide into each other.
Single glider.
Several gliders (128 × 128 cells).
More gliders (512 × 512 cells).
Higher-order structures emerge (2048 × 2048 cells).
Wave-like triangular patterns (4096 × 4096 cells).
Bursts of activity occasionally emerge within the grid at an even larger scale (10240 × 10240 cells).
For comparison, a non-coarsed-grained example for a large grid. Structures are barely visible (4096 × 4096 cells).

More examples

A few gliders (128 × 128 cells).
More gliders (512 × 512 cells).
Larger triangular structures begin to appear(2048 × 2048 cells).
Glider guns form very large structures spanning hundreds of thousands of cells. These very large structures were not visible before (10240 × 10240 cells).

A few gliders (128 × 128 cells).
More gliders (512 × 512 cells).
Larger triangular structures begin to appear(2048 × 2048 cells).
Glider guns form very large structures spanning hundreds of thousands of cells. These very large structures were not visible before (10240 × 10240 cells).

Acknowledgements

This work was partially supported the EU Structural and Investment Funds, Operational Programe Research, Development and Education under the project IMPACT (reg.\ no. CZ.02.1.01/0.0/0.0/15 003/0000468), and the French government under management of Agence Nationale de la Recherche as part of the "Investissements d'avenir" program, reference ANR-19-P3IA-0001 (PRAIRIE 3IA Institute).

Copyright Notice

The documents contained in these directories are included by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a non-commercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright.