The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970. It is a zero-player game, meaning that its evolution is determined by its initial state, requiring no further input. One interacts with the Game of Life by creating an initial configuration and observing how it evolves. It is Turing complete and can simulate a universal constructor or any other Turing machine.
A cellular automaton is a discrete model of computation studied in automata theory. Cellular automata are also called cellular spaces, tessellation automata, homogeneous structures, cellular structures, tessellation structures, and iterative arrays. Cellular automata have found application in various areas, including physics, theoretical biology and microstructure modeling.
A cellular automaton (CA) is Life-like if it meets the following criteria:
In a cellular automaton, a Garden of Eden is a configuration that has no predecessor. It can be the initial configuration of the automaton but cannot arise in any other way. John Tukey named these configurations after the Garden of Eden in Abrahamic religions, which was created out of nowhere.
A continuous automaton can be described as a cellular automaton extended so the valid states a cell can take are not just discrete, but continuous, for example, the real number range [0,1]. The cells however remain discretely separated from each other. One example is called computational verb cellular network (CVCN), of which the states of cells are in the region of [0,1].
Tommaso Toffoli is an Italian-American professor of electrical and computer engineering at Boston University where he joined the faculty in 1995. He has worked on cellular automata and the theory of artificial life, and is known for the invention of the Toffoli gate.
A second-order cellular automaton is a type of reversible cellular automaton (CA) invented by Edward Fredkin where the state of a cell at time t depends not only on its neighborhood at time t − 1, but also on its state at time t − 2.
A block cellular automaton or partitioning cellular automaton is a special kind of cellular automaton in which the lattice of cells is divided into non-overlapping blocks and the transition rule is applied to a whole block at a time rather than a single cell. Block cellular automata are useful for simulations of physical quantities, because it is straightforward to choose transition rules that obey physical constraints such as reversibility and conservation laws.
A cyclic cellular automaton is a kind of cellular automaton rule developed by David Griffeath and studied by several other cellular automaton researchers. In this system, each cell remains unchanged until some neighboring cell has a modular value exactly one unit larger than that of the cell itself, at which point it copies its neighbor's value. One-dimensional cyclic cellular automata can be interpreted as systems of interacting particles, while cyclic cellular automata in higher dimensions exhibit complex spiraling behavior.
Langton's loops are a particular "species" of artificial life in a cellular automaton created in 1984 by Christopher Langton. They consist of a loop of cells containing genetic information, which flows continuously around the loop and out along an "arm", which will become the daughter loop. The "genes" instruct it to make three left turns, completing the loop, which then disconnects from its parent.
In cellular automata, the von Neumann neighborhood is classically defined on a two-dimensional square lattice and is composed of a central cell and its four adjacent cells. The neighborhood is named after John von Neumann, who used it to define the von Neumann cellular automaton and the von Neumann universal constructor within it. It is one of the two most commonly used neighborhood types for two-dimensional cellular automata, the other one being the Moore neighborhood.
Cellular automata, as with other multi-agent system models, usually treat time as discrete and state updates as occurring synchronously. The state of every cell in the model is updated together, before any of the new states influence other cells. In contrast, an asynchronous cellular automaton is able to update individual cells independently, in such a way that the new state of a cell affects the calculation of states in neighbouring cells.
A quantum cellular automaton (QCA) is an abstract model of quantum computation, devised in analogy to conventional models of cellular automata introduced by John von Neumann. The same name may also refer to quantum dot cellular automata, which are a proposed physical implementation of "classical" cellular automata by exploiting quantum mechanical phenomena. QCA have attracted a lot of attention as a result of its extremely small feature size and its ultra-low power consumption, making it one candidate for replacing CMOS technology.
Rule 184 is a one-dimensional binary cellular automaton rule, notable for solving the majority problem as well as for its ability to simultaneously describe several, seemingly quite different, particle systems:
The Curtis–Hedlund–Lyndon theorem is a mathematical characterization of cellular automata in terms of their symbolic dynamics. It is named after Morton L. Curtis, Gustav A. Hedlund, and Roger Lyndon; in his 1969 paper stating the theorem, Hedlund credited Curtis and Lyndon as co-discoverers. It has been called "one of the fundamental results in symbolic dynamics".
Mobile automaton within theoretical computer science, is a class of automata similar to cellular automata but which have a single "active" cell instead of updating all cells in parallel. In a mobile automaton, the evolution rules apply only to the active cell, and also specify how the active cell moves from one generation to the next. All cells that are not active remain the same from one generation to the next. Mobile automata can therefore be considered a hybrid between elementary cellular automata and Turing machines.
The movable cellular automaton (MCA) method is a method in computational solid mechanics based on the discrete concept. It provides advantages both of classical cellular automaton and discrete element methods. One important advantage of the MCA method is that it permits direct simulation of material fracture, including damage generation, crack propagation, fragmentation, and mass mixing. It is difficult to simulate these processes by means of continuum mechanics methods, so some new concepts like peridynamics are required. Discrete element method is very effective to simulate granular materials, but mutual forces among movable cellular automata provides simulating solids behavior. As the cell size of the automaton approaches zero, MCA behavior approaches classical continuum mechanics methods. The MCA method was developed in the group of S.G. Psakhie
A reversible cellular automaton is a cellular automaton in which every configuration has a unique predecessor. That is, it is a regular grid of cells, each containing a state drawn from a finite set of states, with a rule for updating all cells simultaneously based on the states of their neighbors, such that the previous state of any cell before an update can be determined uniquely from the updated states of all the cells. The time-reversed dynamics of a reversible cellular automaton can always be described by another cellular automaton rule, possibly on a much larger neighborhood.
Stochastic cellular automata or probabilistic cellular automata (PCA) or random cellular automata or locally interacting Markov chains are an important extension of cellular automaton. Cellular automata are a discrete-time dynamical system of interacting entities, whose state is discrete.
In cellular automata, a replicator is a pattern that produces copies of itself.
