Cellular automaton
A cellular automaton consists of a regular grid of cells, each in one of a finite number of states, such as on and off (in contrast to a coupled map lattice).
The concept was originally discovered in the 1940s by Stanislaw Ulam and John von Neumann while they were contemporaries at Los Alamos National Laboratory.
One way to simulate a two-dimensional cellular automaton is with an infinite sheet of graph paper along with a set of rules for the cells to follow.
Stanislaw Ulam, while working at the Los Alamos National Laboratory in the 1940s, studied the growth of crystals, using a simple lattice network as his model.
[8] At the same time, John von Neumann, Ulam's colleague at Los Alamos, was working on the problem of self-replicating systems.
The driving concept of the method was to consider a liquid as a group of discrete units and calculate the motion of each based on its neighbors' behaviors.
[15] Von Neumann gave an existence proof that a particular pattern would make endless copies of itself within the given cellular universe by designing a 200,000 cell configuration that could do so.
The original work of Wiener and Rosenblueth contains many insights and continues to be cited in modern research publications on cardiac arrhythmia and excitable systems.
In 1969, Gustav A. Hedlund compiled many results following this point of view[20] in what is still considered as a seminal paper for the mathematical study of cellular automata.
In 1969, German computer pioneer Konrad Zuse published his book Calculating Space, proposing that the physical laws of the universe are discrete by nature, and that the entire universe is the output of a deterministic computation on a single cellular automaton; "Zuse's Theory" became the foundation of the field of study called digital physics.
[25] In the 1970s a two-state, two-dimensional cellular automaton named Game of Life became widely known, particularly among the early computing community.
Invented by John Conway and popularized by Martin Gardner in a Scientific American article,[26] its rules are as follows: Despite its simplicity, the system achieves an impressive diversity of behavior, fluctuating between apparent randomness and order.
It is possible to arrange the automaton so that the gliders interact to perform computations, and after much effort it has been shown that the Game of Life can emulate a universal Turing machine.
[27] It was viewed as a largely recreational topic, and little follow-up work was done outside of investigating the particularities of the Game of Life and a few related rules in the early 1970s.
[28] Stephen Wolfram independently began working on cellular automata in mid-1981 after considering how complex patterns seemed formed in nature in violation of the second law of thermodynamics.
[29] He published his first paper in Reviews of Modern Physics investigating elementary cellular automata (Rule 30 in particular) in June 1983.
[31] Wolfram, in A New Kind of Science and several papers dating from the mid-1980s, defined four classes into which cellular automata and several other simple computational models can be divided depending on their behavior.
[47] Reversible cellular automata are often used to simulate such physical phenomena as gas and fluid dynamics, since they obey the laws of thermodynamics.
One important example is reaction–diffusion textures, differential equations proposed by Alan Turing to explain how chemical reactions could create the stripes on zebras and spots on leopards.
Rule 30 exhibits class 3 behavior, meaning even simple input patterns such as that shown lead to chaotic, seemingly random histories.
In the course of the development of A New Kind of Science, as a research assistant to Wolfram in 1994, Matthew Cook proved that some of these structures were rich enough to support universality.
These include phenomena of great medical importance, such as: The Belousov–Zhabotinsky reaction is a spatio-temporal chemical oscillator that can be simulated by means of a cellular automaton.
In the 1950s A. M. Zhabotinsky (extending the work of B. P. Belousov) discovered that when a thin, homogenous layer of a mixture of malonic acid, acidified bromate, and a ceric salt were mixed together and left undisturbed, fascinating geometric patterns such as concentric circles and spirals propagate across the medium.
In the "Computer Recreations" section of the August 1988 issue of Scientific American,[69] A. K. Dewdney discussed a cellular automaton[70] developed by Martin Gerhardt and Heike Schuster of the University of Bielefeld (Germany).
Probabilistic cellular automata are used in statistical and condensed matter physics to study phenomena like fluid dynamics and phase transitions.
By adjusting the parameters of the model, the proportion of cells being in the same state can be varied, in ways that help explicate how ferromagnets become demagnetized when heated.
[74][75] The phase transition in the two-dimensional Ising model and other systems in its universality class has been of particular interest, as it requires conformal field theory to understand in depth.
Besides the attachment/detachment events being encoded in the rules of the CA, the adatoms on top of the vicinal form a thin layer, and their thermal motion is modeled by a Monte Carlo module.
[81] The vicCA model was extensively used by Alexey Redkov[82] to develop a Machine Learning algorithm on top of it, significantly speeding up calculations by a factor of 10⁵ while enabling systematic classification of the observed phenomena.
[89] For a random starting pattern, these maze-generating cellular automata will evolve into complex mazes with well-defined walls outlining corridors.
