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.
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.
Gerlee, P., & Anderson, A. R. A. (2007). An evolutionary hybrid cellular automaton model of solid tumour growth. Journal of Theoretical Biology, 246(4), 583–603. https://doi.org/10/dm5dqw
Wolfram, S. (1984). Universality and complexity in cellular automata. Physica D: Nonlinear Phenomena, 10(1), 1–35. https://doi.org/10/fkcg4x
We use (a small number of) cookies to improve the usability of this website. Read more about them in our Privacy Policy and our
Functional Always active
The technical storage or access is strictly necessary for the legitimate purpose of enabling the use of a specific service explicitly requested by the subscriber or user, or for the sole purpose of carrying out the transmission of a communication over an electronic communications network.
Preferences
The technical storage or access is necessary for the legitimate purpose of storing preferences that are not requested by the subscriber or user.
Statistics
The technical storage or access that is used exclusively for statistical purposes.The technical storage or access that is used exclusively for anonymous statistical purposes. Without a subpoena, voluntary compliance on the part of your Internet Service Provider, or additional records from a third party, information stored or retrieved for this purpose alone cannot usually be used to identify you.
Third-party
The technical storage or access is required to create user profiles to send advertising, or to track the user on a website or across several websites for similar marketing purposes.