- tags
- Emergence, Chaos, Artificial Intelligence
- resources
- Wikipedia, (Von Neumann and Burks 1966; Wolfram 2002)

## Definition

A cellular automaton is a computational model defined with
respect to a regular grid of individual elements (called
*cells*). Each of those cells can be in one of a finite
number of states — *alive* or *dead*, \(\{1, 2,
3\}\), etc.

A cellular automaton’s evolution is simulated in discrete
timesteps. At each new timestep, cells are updated according to a
local **evolution rule**. The rule is a table or
function mapping every possible state of a cell and their local
neighborhoods to a new state.

There are multiple ways to define the topology of the grid, rules, local neighborhoods and simulation steps. Some well known types of automata are listed below

### Elementary cellular automata

Cellular automata on 1D grids, with two states and neighborhood radius 1 (middle cell + one cell on each side) are called Elementary cellular automata — or ECA.

### Reversible cellular automata

Reversible cellular automata are CA rules with one and only one image and pre-image. Each step of the evolution is reversible.

### Cyclic cellular automata

## Cellular automata and Reaction-diffusion systems

I just realized that cellular automata and reaction-diffusion systems are strongly related. This might be a well known fact but it seemed particularly striking when looking at the following image from (Manukyan et al. 2017) it seems clear that there is a continuum between the two models.

## Cellular automata in Image processing

Papers about using cellular automata in image processing (Selvapeter and Hordijk 2009; Wongthanavasu and Ponkaew 2013)

Some cellular automata have a characteristic “blob-preserving” behavior where parts of the space get organized in large blobs. This behavior is very similar to an application of local median. See this twitter link for an animated example.

## Coarse-graining CA

I am very attracted to this idea of coarse graining CAs. This is reminiscent of physical systems where the inner working of a system are mostly opaque to an observer and we only see a complex macro-behavior. In the case of CAs this might be the key to overcoming this problem of seemingly impossible increase of complexity beyond a certain point if we keep looking at individual cells. This also allows an external observer to understand a complex behavior happening in billions of cells visually. It can be done with Autoencoders.

## CA as regular languages

CAs can be studied with regular languages.

## Evolution and CAs

Why would things evolve in a CA?
I was running interesting CAs for several 100s of thousands of
steps recently and realized that I did not really know what I would
be expecting to happen in one of those without any input from
outside. Could it be that, by just pure luck, some things start to
evolve in it? That some species or *life-like forms*
emerge?

If this is even possible, what are the odds of this happening? Was it how it worked in our case (earth)? Did just random particle interactions in a large soup gave rise to a complete miracle? So far from my experiment I have seen complex previously unseen structures emerge during an automaton evolution, but this has never gone farther than just a few big structures appearing and not staying this way. I believe it is a bias to think that those structures would have been suited to keep evolving because their brittleness did not let them survive. Therefore the (unpractical) way forward might be to let those things run and see what happens, where the “surviving” would be the ones left after all this.

I’m wondering whether some kind of external input to those small
“universe” could help give rise to more complex behavior. Because I
am starting to think that even with the most efficient system
possible, the probability of seeing a complex structure appearing decreases
somewhat exponentially with the *complexity* of the
structure (or according to a power law).

Obviously I have no idea about all this and this is just based on speculation. But I’ve yet to see reasonable evidence that we can run a CA for a large number of time steps without any kind of input and see this increase in complexity happen by itself. Maybe the key would be to help it? But is it even possible?

### Playing god with cellular automata

I believe an exciting part of working on spontaneous emergence,
artificial evolution, and cellular automata is the fact that it
really feels like playing with a *microverse*. Some relevant
recent pop-cultures examples involving this idea include:

- Rick and morty Season 2 Episode 6: The Ricks Must Be Crazy
- Love, Death & Robot Episode 16: Ice Age

Each one of those cellular automata can be seen as a universe, with its own laws of physics (update rule) and initial big bang-like configuration (the initial state). Most combinations of the laws of physics are not stable and create completely disordered systems, but some rare configurations give rise to large structures sifting through space and exhibit highly non-trivial macro behavior (2-3 cells wide up to several 100s of cells-wide). Many of these structures interact in different ways, some create siblings and children structures while other get destroyed very quickly.

This transition from randomness to order could be seen in the case of our universe as the 4 physical forces pulling together particles into bigger and bigger structures which form a large system with a lot of emptiness and some localized structures. In this analogy, our planet and even our galaxy are just a microscopic ripple on of those giant structures, but what if we could make this kind of ripple happen in a much smaller universe, with much simpler laws? This is more or less what we are trying to achieve with cellular automata.

Obviously starting from scratch is hard, and it might not be
necessary to let this *microverse* evolve in a closed way
without interacting with it somehow.

This point of view is related to The Simulated reality hypothesis and Zuse’s thesis, and is an interesting argument for the universe being a computer simulation — and even a CA.

## Bibliography

Manukyan, Liana, Sophie A. Montandon,
Anamarija Fofonjka, Stanislav Smirnov, and Michel C. Milinkovitch.
2017. “A Living Mesoscopic Cellular Automaton Made of Skin Scales.”
*Nature* 544 (7649):173–79.

Selvapeter, P. Jebaraj, and Wim Hordijk.
2009. “Cellular Automata for Image Noise Filtering.” In *2009
World Congress on Nature & Biologically Inspired Computing
(NaBIC)*, 193–97. Coimbatore, India: IEEE.

Von Neumann, John, and Arthur W. Burks.
1966. “Theory of Self-Reproducing Automata.” *IEEE Transactions
on Neural Networks* 5 (1):3–14.

Wolfram, Stephen. 2002. *A New Kind of
Science*. Champaign, IL: Wolfram Media.

Wongthanavasu, Sartra, and Jetsada
Ponkaew. 2013. “Cellular Automata for Pattern Recognition.” In
*Emerging Applications of Cellular Automata*, edited by
Alejandro Salcido. InTech.

## Backlinks

- Lenia
- Boltzmann brain
- Amorphous computing
- Cellular automata as regular languages
- Cellular neural networks
- Talk: Alife 2020 keynote Lee Cronin - A Top Down Chemically Embodied Artificial Life Computation
- Automated discovery in complex systems
- Abelian sandpile model
- Elementary cellular automata
- Turing completeness of cellular automata
- Complexity of cellular automata
- Zuse’s thesis
- Langton’s loop
- Reversible cellular automata
- Notes on: Developmental mappings and phenotypic complexity by Lehre, P. K., & Haddow, P. C. (2003)
- Notes on: The information theory of individuality by Krakauer, D., Bertschinger, N., Olbrich, E., Flack, J. C., & Ay, N. (2020)
- Notes on: Growing Neural Cellular Automata by Mordvintsev, A., Randazzo, E., Niklasson, E., & Levin, M. (2020)
- Notes on: Evolution in asynchronous cellular automata by Nehaniv, C. L. (2003)
- Notes on: An Integrated Perspective on the Constitutive and Interactive Dimensions of Autonomy by Beer, R. D. (2020)
- Notes on: Resilient Life: An Exploration of Perturbed Autopoietic Patterns in Conway’s Game of Life by Cika, A., Cohen, E., Kruszewski, G., Seet, L., Steinmann, P., & Yin, W. (2020)
- Notes on: A new structurally dissolvable self-reproducing loop evolving in a simple cellular automata space by Sayama, H. (1999)
- Notes on: Transition phenomena in cellular automata rule space by Li, W., Packard, N. H., & Langton, C. G. (1990)
- Notes on: Evolving a self-repairing, self-regulating, French flag organism by Miller, J. F. (2004)
- Notes on: Intrinsically Motivated Discovery of Diverse Patterns in Self-Organizing Systems by Reinke, C., Etcheverry, M., & Oudeyer, P. (2020)
- Crosshatch automata
- Reservoir computing
- Conway’s Game of Life
- Konrad Zuse
- Computing in cellular automata
- Cellular automata as CNNs
- Open-ended Evolution
- Von Neumann’s self-reproducing CA
- Boolean networks