A cellular automaton (plural: cellular automata) is composed of a grid of cells. Traditionally, cells can be in a finite number of discrete states, although some more modern variations on cellular automata have changed this rule. A set of global rules determine how cells transition from state to state as time advances. Often, these update rules depend on the state of nearby cells. Cellular automata are used to study a range of question in biology, physics, computer science, and complexity theory.
Discrete cellular automata
Classically, all cellular automata are discrete systems with a finite number of states. Time steps are also discrete; at each time step, the next state for each cell is calculated. These state changes are then applied on the next time step. Cellular automata were first created by Stanislaw Ulam and John von Neumann, but did not become popular until John Conway created Conway’s Game of Life in the 1970’s. Conway’s Game of Life is still by far the most well known cellular automaton.
To facilitate their use in the study of complexity, Stephen Wolfram came up with a way of classifying them into different complexity classes . These classes can be broadly described as follows:
- Class 1: Almost all initial states will lead to a homogeneous state within a finite number of time steps.
- Class 2: Almost all initial states will lead to a pattern (either stable or oscillating).
- Class 3: Almost all initial states will lead to a chaotic state.
- Class 4: Almost all initial states will lead to the emergence of complex structures that interact with each other in interesting ways.
Some class 4 cellular automata, including Conway’s Game of Life, have been shown to be capable of implementing a Turing machine. Thus, they are theoretically capable of performing any computation. That said, such behaviors generally must be built by hand as they are unlikely to emerge naturally.
Hybrid cellular automata
Hybrid cellular automata pair a discrete grid with a continuous environment . These models were originally developed (and are still primarily used) for studying cancer evolution. In this context, the discrete portion represents the cancer cells and the continuous portion represents a gradient of a relevant chemical. The cells in the discrete portion can affect the corresponding region of the continuous portion and vica versa. In most cases, there is a separation of time scales between the two portions of the model, with the continuous portion updating many times for every discrete time step in order to appropriately model diffusion.
Continuous cellular automata
Lenia is the primary example of a continuous cellular automaton system . Rather than forcing each cell to be in a discrete state, states are instead represented by continuous numbers. This small change allows for a rich and visually striking system.
For a lesson on how to code both discrete and continuous cellular automata, see: https://colab.research.google.com/github/OpenLenia/Lenia-Tutorial/blob/main/Tutorial_From_Conway_to_Lenia.ipynb
Multiple Neighborhood Cellular Automata
Multiple Neighborhood Cellular Automata (MNCA) were invented in 2014 by “Slackermanz” . They define multiple update rules that rely on different neighborhoods around a focal cell to determine its state.
Further Resources
- A browser-based program for writing your own CA is available from Rocky Li.
- Growing Neural Cellular Automata interactive tutorial